home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / INFO / FAQC9402.ZIP / compress.faq
Text File  |  1994-02-21  |  198KB  |  4,364 lines
  1. Article: 9668 of comp.compression
  2. Path: chorus!chorus.fr
  3. From: jloup@chorus.fr (Jean-loup Gailly)
  4. Newsgroups: comp.compression,comp.compression.research,news.answers,comp.answers
  5. Subject: comp.compression Frequently Asked Questions (part 1/3)
  6. Summary: *** READ THIS BEFORE POSTING ***
  7. Keywords: data compression, FAQ
  8. Message-ID: <compr1_21feb94@chorus.fr>
  9. Date: 21 Feb 94 16:54:26 GMT
  10. Expires: 30 Mar 94 16:17:20 GMT
  11. Sender: news@chorus.chorus.fr
  12. Reply-To: jloup@chorus.fr
  13. Followup-To: comp.compression
  14. Lines: 2569
  15. Approved: news-answers-request@MIT.Edu
  16. Supersedes: <compr1_17jan94@chorus.fr>
  17. Xref: chorus comp.compression:9668 comp.compression.research:1189 news.answers:17958 comp.answers:3823
  18.  
  19.  
  20. Archive-name: compression-faq/part1
  21. Last-modified: Feb 21st, 1994
  22.  
  23.         "I've already explained this once, but repetition is
  24.         the very soul of the net."        (from alt.config)
  25.  
  26. This file is part 1 of a set of Frequently Asked Questions (FAQ) for
  27. the groups comp.compression and comp.compression.research.  If you
  28. can't find part 2 or 3, see item 53 below. A copy of this FAQ is available
  29. by ftp in rtfm.mit.edu:/pub/usenet/news.answers/compression-faq/part[1-3].
  30.  
  31. Certain questions get asked time and again, and this is an attempt to
  32. reduce the bandwidth taken up by these posts and their associated
  33. replies.  If you have a question, *please* check this file before you
  34. post.  It may save a lot of peoples time.
  35.  
  36. If you have not already read the overall Usenet introductory material
  37. posted to "news.announce.newusers", please do. It is also available by
  38. ftp in garbo.uwasa.fi:/pc/doc-net/usenews.zip (see item 2 below about .zip).
  39.  
  40. If you don't want to see this FAQ regularly, please add the subject
  41. line to your kill file. (If you don't know what a kill file is, get
  42. by ftp the file rtfm.mit.edu:/pub/usenet/news.answers/killfile-faq.)
  43. If you have corrections or suggestions for this FAQ, send them to
  44. Jean-loup Gailly <jloup@chorus.fr>.  Thank you.
  45.  
  46. Part 1 is oriented towards practical usage of compression programs.
  47. Part 2 is more intended for people who want to know how compression works.
  48. Part 3 is a long list of image compression hardware.
  49.  
  50. Main changes relative to the previous version: 
  51.  
  52. - replace all references to wsmr-simtel20 with oak.oakland.edu
  53. - added note about pkzip 2.06 (item 3)
  54. - added pointer to gopher server for CCITT documents (item 11)
  55. - added an MPEG audio compressor (item 26)
  56. - added pointer to some medical images (item 55)
  57.  
  58.  
  59. Contents
  60. ========
  61.  
  62. General questions:
  63.  
  64. [1]  What are these newsgroups about?
  65. [2]  What is this .xxx file type?
  66.      Where can I find the corresponding compression program?
  67. [3]  What is the latest pkzip version?
  68. [4]  What is an archiver?
  69. [5]  What is the best general purpose compression program?
  70. [7]  Which books should I read?
  71. [8]  What about patents on data compression algorithms?
  72. [9]  The WEB 16:1 compressor.
  73. [11] What is the V.42bis standard?
  74. [12] I need source for the winners of the Dr Dobbs compression contest
  75. [13] I need source for arithmetic coding
  76.  
  77. Image and audio compression:
  78.  
  79. [15] Where can I get image compression programs?
  80. [16] What is the state of the art in lossless image compression?
  81. [17] What is the state of fractal compression?
  82. [18] I need specs and source for TIFF and CCITT group 4 Fax.
  83. [19] What is JPEG?
  84. [20] I am looking for source of an H.261 codec and MPEG
  85. [25] Fast DCT (Discrete Cosine Transform) algorithms
  86. [26] Are there algorithms and standards for audio compression?
  87.  
  88. Common problems:
  89.  
  90. [30] My archive is corrupted!
  91. [31] pkunzip reports a CRC error!
  92. [32] VMS zip is not compatible with pkzip!
  93. [33] I have a problem with Stacker!
  94.  
  95. Questions which do not really belong to comp.compression:
  96.  
  97. [50] What is this 'tar' compression program?
  98. [51] I need a CRC algorithm
  99. [52] What about those people who continue to ask frequently asked questions?
  100. [53] Where are FAQ lists archived?
  101. [54] I need specs for graphics formats
  102. [55] Where can I find Lenna and other images?
  103. [56] I am looking for a message digest algorithm
  104.  
  105.  
  106. Part 2: (Long) introductions to data compression techniques
  107.  
  108. [70] Introduction to data compression (long)
  109.        Huffman and Related Compression Techniques
  110.        Arithmetic Coding
  111.        Substitutional Compressors
  112.           The LZ78 family of compressors
  113.           The LZ77 family of compressors
  114.  
  115. [71] Introduction to MPEG (long)
  116.        What is MPEG?
  117.        Does it have anything to do with JPEG?
  118.        Then what's JBIG and MHEG?
  119.        What has MPEG accomplished?
  120.        So how does MPEG I work?
  121.        What about the audio compression?
  122.        So how much does it compress?
  123.        What's phase II?
  124.        When will all this be finished?
  125.        How do I join MPEG?
  126.        How do I get the documents, like the MPEG I draft?
  127.  
  128. [72] What is wavelet theory?
  129. [73] What is the theoretical compression limit?
  130. [74] Introduction to JBIG
  131. [75] Introduction to JPEG
  132. [76] What is Vector Quantization?
  133.  
  134.  
  135. Part 3: (Long) list of image compression hardware
  136.  
  137. [85] Image compression hardware
  138. [99] Acknowledgments
  139.  
  140.  
  141. Search for "Subject: [#]" to get to question number # quickly. Some news
  142. readers can also take advantage of the message digest format used here.
  143.  
  144. If you know very little about data compression, read question 70 in
  145. part 2 first.
  146.  
  147. ------------------------------------------------------------------------------
  148.  
  149. Subject: [1] What are these newsgroups about?
  150.  
  151.  
  152. comp.compression is the place to discuss about data compression, both
  153. lossless (for text or data) and lossy (for images, sound, etc..).
  154. comp.compression.research was created later to provide a forum for
  155. current research on data compression and data compression algorithms;
  156. this group is now moderated. If you are not experienced in data compression,
  157. please post in comp.compression only.
  158.  
  159. If you only want to find a particular compression program for a
  160. particular operating system, please read first this FAQ and the
  161. article "How to find sources" which is regularly posted in
  162. news.answers.
  163.  
  164. If you can't resist posting such a request, other groups are probably
  165. more appropriate (comp.binaries.ibm.pc.wanted, comp.os.msdos.apps,
  166. comp.sources.wanted, comp.sys.mac.wanted, comp.archives.msdos.d,
  167. alt.graphics.pixutils). Please post your request in comp.compression
  168. only as a last resource.
  169.  
  170. If your question is about graphics only (no compression), please
  171. post to comp.graphics, *after* reading the comp.graphics FAQ (see
  172. item 54 below). For some unknown reason, many questions about
  173. graphics are incorrectly posted to comp.compression.
  174. For questions related to audio compression, check also comp.dsp.
  175.  
  176. Please do not post any program in binary form to comp.compression.
  177. Very short sources can be posted, but long sources should be be posted
  178. to the specialized source groups, such as comp.sources.* or alt.sources.
  179.  
  180. As for any newsgroups, do not post the same message separately to
  181. comp.compression and comp.compression.research.
  182.  
  183. ------------------------------------------------------------------------------
  184.  
  185. Subject: [2] What is this .xxx file type?
  186.              Where can I find the corresponding compression program?
  187.  
  188.  
  189. All the programs mentioned in this section are lossless.
  190. For most programs, one US and one European ftp site are given.
  191. (oak.oakland.edu: 141.210.10.117, garbo.uwasa.fi: 128.214.87.1)
  192. Many other sites (in particular wuarchive.wustl.edu: 128.152.135.4)
  193. have the same programs.
  194.  
  195. To keep this list to a reasonable size, many programs are not
  196. mentioned here. Additional information can be found in the file
  197. ftp.cso.uiuc.edu:/doc/pcnet/compression [128.174.5.61] maintained by
  198. David Lemson (lemson@uiuc.edu). When several programs can handle
  199. the same archive format, only one of them is given.
  200.  
  201. Sources for additional lossless data compressors can be found in
  202. garbo.uwasa.fi:/pc/programming/lds_11.zip and
  203. oak.oakland.edu:/pub/msdos/archivers/lz-comp2.zip.
  204. Sources in Pascal are in garbo.uwasa.fi:/pc/turbopas/preskit2.zip.
  205.  
  206. For Macintosh programs, look on sumex-aim.stanford.edu:/info-mac [36.44.0.6].
  207. For VM/CMS, look on vmd.cso.uiuc.edu:/public.477 [128.174.5.98].
  208. For Atari, look on atari.archive.umich.edu [141.211.165.41]
  209. For Amiga, look on ftp.cso.uiuc.edu:/pub/amiga [128.174.5.59]
  210.     
  211. If you don't know how to use ftp or don't have ftp access, read the
  212. article "How to find sources" which is regularly posted in news.answers.
  213.  
  214. If you can't find a program given below, it is likely that a newer
  215. version exists in the same directory. (Tell me <jloup@chorus.fr>)
  216.  
  217. A very short description of the compression algorithm is given for
  218. most programs. For the meaning of LZ77, LZ78 and LZW, see question 70
  219. in part 2 of the FAQ.) If you are looking for the file format of a
  220. specific compression program, get the sources of the decompressor.
  221.  
  222. ext:  produced by or read by
  223.  
  224. .arc: arc, pkarc for MSDOS. (LZW algorithm)
  225.     wuarchive.wustl.edu:/mirrors/msdos/starter/pk361.exe
  226.     garbo.uwasa.fi:/pc/arcers/pk361.exe
  227.  
  228.       arc for Unix
  229.         wuarchive.wustl.edu:/mirrors/misc/unix/arc521e.tar-z
  230.     garbo.uwasa.fi:/unix/arcers/arc.tar.Z
  231.         Contact: Howard Chu <hyc@umix.cc.umich.edu>
  232.  
  233.       arc for VMS
  234.     wuarchive.wustl.edu:/packages/compression/vax-vms/arc.exe
  235.  
  236.       arcmac for Mac
  237.     mac.archive.umich.edu:/mac/utilities/compressionapps/arcmac.hqx
  238.  
  239.       arc for Amiga
  240.     ftp.funet.fi:pub/amiga/fish/001-100/ff070/arc.lha
  241.  
  242. .arj: arj for MSDOS (LZ77 with hashing, plus secondary static Huffman
  243.           encoding on a block basis)
  244.         Contact: Robert K Jung <robjung@world.std.com>
  245.         wuarchive.wustl.edu:/mirrors/msdos/archivers/arj241a.exe
  246.     garbo.uwasa.fi:/pc/arcers/arj241a.exe
  247.  
  248.       unarj for Unix. Decompresses only. (There is no arj compressor for Unix.
  249.         Don't post a request.)
  250.         wuarchive.wustl.edu:/mirrors/misc/unix/unarj241.tar-z
  251.     garbo.uwasa.fi:/unix/arcers/unarj241.tar.Z
  252.  
  253.       unarj for Mac
  254.         mac.archive.umich.edu:/mac/util/compression/unarjmac.cpt.hqx      
  255.  
  256.       unarj for Amiga
  257.     ftp.funet.fi:pub/amiga/utilities/archivers/unarj-0.5.lha
  258.  
  259. .bck: VMS BACKUP. BACKUP is *not* a compression program. Do "help backup".
  260.  
  261. .cpt: Compact Pro for Mac
  262.         sumex-aim.stanford.edu:/info-mac/util/compact-pro-133.hqx [36.44.0.6]
  263.  
  264.       For Unix:
  265.     sumex-aim.stanford.edu:/info-mac/unix/macutil-20b1.shar
  266.         ftp.cwi.nl:/pub/macutil2.0b3.shar.Z
  267.  
  268. .exe: self-extracting MSDOS executable (creates files on disk when run)
  269.       Run the file, or try unzip, lha or arj on it.
  270.  
  271. .exe: compressed MSDOS executable (decompresses itself in memory then runs
  272.       the decompressed code). To get the original uncompressed .exe:
  273.         oak.oakland.edu:/pub/msdos/execomp/unp315.zip
  274.       To create such files:
  275.         oak.oakland.edu:/pub/msdos/execomp/lzexe91e.zip
  276.     nic.funet.fi:/pub/msdos/windows/util/winlite1.zip (for Windows exe)
  277.  
  278. .gif: gif files are images compressed with the LZW algorithm. See the
  279.       comp.graphics FAQ list for programs manipulating .gif files. See
  280.       suffix .Z below for source of LZW.
  281.  
  282. .gz, .z:  gzip (or pack, see .z below). gzip uses the same algorithm as
  283.           zip 2.0 (see below); it can also extract packed and compressed files.
  284.       For Unix, MSDOS, OS/2, VMS, Atari, Amiga, Primos:
  285.     prep.ai.mit.edu:/pub/gnu/gzip-1.2.4.tar  (or .shar or .tar.gz : source)
  286.     prep.ai.mit.edu:/pub/gnu/gzip-msdos-1.2.4.exe (MSDOS, lha self-extract)
  287.     garbo.uwasa.fi:/unix/arcers/gzip-1.2.4.tar.Z  (source)
  288.     garbo.uwasa.fi:/pc/unix/gzip124.zip           (MSDOS exe, self-extract)
  289.     ftp.uu.net:/pub/archiving/zip/VMS/gzip123x.exe (VMS exe)
  290.         mac.archive.umich.edu:/mac/util/compression/macgzip0.2.cpt.hqx (Mac)
  291.         mac.archive.umich.edu:/mac/development/source/macgzip0.2src.cpt.hqx
  292.  
  293. .ha:  ha 0.98 for MSDOS (improved PPMC - 4th order Markov modeling)
  294.     garbo.uwasa.fi:/pc/arcers/ha098.exe
  295.  
  296. .hqx: Macintosh BinHex format.. (BinHex is *not* a compression program,
  297.     it is similar to uuencode but handles multiple forks.)
  298.        for Mac:
  299.      mac.archive.umich.edu:/mac/utilities/compressionapps/binhex4.0.bin
  300.  
  301.        for Unix:
  302.          sumex-aim.stanford.edu:/info-mac/cmp/mcvert-212.shar [36.44.0.6]
  303.  
  304.        for MSDOS:
  305.          wuarchive.wustl.edu:/mirrors/msdos/xbin23.zip
  306.  
  307. .lha:
  308. .lzh: lha for MSDOS (LZ77 with a trie data structure, plus secondary static
  309.           Huffman coding on a block basis)
  310.     oak.oakland.edu:/pub/msdos/archiver/lha213.exe   (exe)
  311.     oak.oakland.edu:/pub/msdos/archiver/lha211sr.zip (sources)
  312.     garbo.uwasa.fi:/pc/arcers/lha255b.exe
  313.  
  314.       lharc for Unix. (LZ77 with hash table and binary trees, plus secondary
  315.           Huffman coding)
  316.            Warning: lharc can extract .lzh files created by
  317.            lharc 1.xx but not those created by lha. See lha for Unix below.
  318.         wuarchive.wustl.edu:/mirrors/misc/unix/lharc102a.tar-z
  319.     garbo.uwasa.fi:/unix/arcers/lharcsrc.zoo
  320.  
  321.       lharc for VMS. Same warning as for Unix lharc.
  322.     wuarchive.wustl.edu:/packages/compression/vax-vms/lharc.exe
  323.  
  324.       lha for Unix. Warning: all doc is in Japanese.
  325.     wuarchive.wustl.edu:/mirrors/misc/unix/lha101u.tar-z
  326.     garbo.uwasa.fi:/unix/arcers/lha-1.00.tar.Z
  327.           Contact: lha-admin@oki.co.jp or oki@wbg.telcom.oki.co.jp
  328.  
  329.       lha for Mac
  330.         mac.archive.umich.edu:/mac/utilities/compressionapps/maclha2.0.cpt.hqx
  331.  
  332.       lha for Amiga
  333.     ftp.funet.fi:pub/amiga/utilities/archivers/LhA_e138.run
  334.  
  335.  
  336. .pak: pak for MSDOS (LZW algorithm)
  337.         wuarchive.wustl.edu:/mirrors/msdos/archivers/pak251.exe
  338.     garbo.uwasa.fi:/pc/arcers/pak251.exe
  339.  
  340. .pit: PackIt (Macintosh)
  341.        for Mac:
  342.          sumex-aim.stanford.edu:/info-mac/util/stuffit-151.hqx  [36.44.0.6]
  343.  
  344.        for Unix:
  345.          sumex-aim.stanford.edu:/info-mac/unix/mcvert-165.shar [36.44.0.6]
  346.  
  347. .pp: PowerPacker (Amiga)
  348.     ftp.funet.fi:pub/amiga/fish/501-600/ff561/PPLib.lha
  349.  
  350. .sea: self-extracting archive (Macintosh)
  351.          Run the file to extract it. The self-extraction code can be
  352.          removed with:
  353.       mac.archive.umich.edu:/mac/utilities/compressionapps/desea1.11.cpt.hqx
  354.  
  355. .sdn: used by the Shareware Distribution Network.
  356.       Try the decompressors for .pak or .arj (see above)
  357.  
  358. .shar:  Shell archive. This is not a compression program. Use "sh foo.shar"
  359.         to extract.
  360.  
  361. .sit: Stuffit for Macintosh
  362.        for Mac:
  363.          sumex-aim.stanford.edu:/info-mac/util/stuffit-lite-30.hqx [36.44.0.6]
  364.  
  365.        for Unix:
  366.          sumex-aim.stanford.edu:/info-mac/cmp/unsit-15-unix.shar [36.44.0.6]
  367.  
  368.        for Amiga:
  369.      ftp.funet.fi:pub/amiga/utilities/archivers/unsit-1.5c2.lha
  370.  
  371.        for MSDOS:
  372.      garbo.uwasa.fi:/pc/arcers/unsit30.zip
  373.  
  374. .?q?: Squeeze for MSDOS (do not confuse with other 'squeeze' below).
  375.       Static Huffman coding.
  376.     oak.oakland.edu:/pub/msdos/starter/sqpc12a.com (squeeze)
  377.     oak.oakland.edu:/pub/msdos/starter/nusq110.com (unsqueeze)
  378.  
  379. .sqz: Squeeze for MSDOS (do not confuse with other 'squeeze' above)
  380.       LZ77 with hashing.
  381.     wuarchive.wustl.edu:/mirrors/msdos/archivers/sqz1083e.exe
  382.         garbo.uwasa.fi:/pc/arcers/sqz1083e.exe
  383.  
  384. .tar: tar is *not* a compression program. However, to be kind for you:
  385.       for MSDOS
  386.     wuarchive.wustl.edu:/mirrors/msdos/starter/tarread.exe
  387.     garbo.uwasa.fi:/pc/unix/tar4dos.zoo
  388.  
  389.       for Unix
  390.         tar (you have it already. To extract: tar xvf file.tar)
  391.  
  392.       for VMS
  393.     wuarchive.wustl.edu:/packages/compression/vax-vms/tar.exe
  394.  
  395.       for Macintosh
  396.         sumex-aim.stanford.edu:/info-mac/util/tar-30.hqx
  397.  
  398.       for Amiga:
  399.     ftp.funet.fi:pub/amiga/fish/401-500/ff445/Tar.lha
  400.  
  401. .tar.Z, .tar-z, .taz: tar + compress
  402.       For Unix:     zcat file.tar.Z | tar xvf -
  403.       with GNU tar: tar xvzf file.tar.Z
  404.       Other OS: first uncompress (see .Z below) then untar (see .tar above)
  405.  
  406. .tar.gz, tar.z, .tgz: tar + gzip
  407.       For Unix: gzip -cd file.tar.gz | tar xvf -
  408.       with GNU tar: tar xvzf file.tar.gz
  409.       Other OS: first uncompress (see .gz above) then untar (see .tar above)
  410.  
  411. .uc2: UC2 for MSDOS and OS/2. (LZ77 with secondary static Huffman encoding on
  412.      a block basis, and dynamic dictionaries shared among files.)
  413.     Contact: desk@aip.nl
  414.       ftp.nl.net:/gopher/NLnet-connected/AIP-NL/uc2ins.exe
  415.  
  416. .z:   pack or gzip (see .gz above). pack uses static Huffman coding.
  417.       To extract, see .gz above.
  418.  
  419. .zip: pkzip 1.10 for MSDOS. (LZ77 with hashing, plus secondary static
  420.           Shannon-Fano encoding on whole file)
  421.            Contact: pkware.inc@mixcom.com
  422.          wuarchive.wustl.edu:/mirrors/msdos/zip/pkz110eu.exe.
  423.          garbo.uwasa.fi:/pc/goldies/pkz110eu.exe.
  424.            Note: pkz110eu.exe is an 'export' version without encryption.
  425.  
  426.       zip 1.1 for Unix, MSDOS, VMS, OS/2, ... (compatible with pkzip 1.10.
  427.      For corresponding unzip, see unzip 5.0p1 below).
  428.      ftp.uu.net:/pub/archiving/zip/zip11.zip
  429.  
  430.       arcutil 2.0 for VM/CMS (unzip only, not yet compatible with pkzip 2.04)
  431.          vmd.cso.uiuc.edu:/public.477/arcutil.* [128.174.5.98].
  432.  
  433.       pkzip 2.04g for MSDOS. (LZ77 with hashing, plus secondary static
  434.            Huffman coding on a block basis)
  435.      oak.oakland.edu:/pub/msdos/zip/pkz204g.exe
  436.          garbo.uwasa.fi:/pc/arcers/pkz204g.exe
  437.  
  438.       zip 2.0.1 and unzip 5.0p1 for Unix, MSDOS, VMS, OS/2, Amiga, ...
  439.           Compatible with pkzip 2.04g (LZ77 with hashing, plus secondary static
  440.           Huffman coding on a block basis)
  441.             Contact: zip-bugs@wkuvx1.bitnet
  442.      ftp.uu.net:/pub/archiving/zip/zip201.zip          (source)
  443.      ftp.uu.net:/pub/archiving/zip/unz50p1.tar.Z       (source)
  444.      ftp.uu.net:/pub/archiving/zip/MSDOS/zip20x.zip    (MSDOS exe)
  445.      ftp.uu.net:/pub/archiving/zip/MSDOS/unz50p1.exe   (MSDOS exe)
  446.      ftp.uu.net:/pub/archiving/zip/VMS/unz50p1x.exe    (Vax/VMS exe)
  447.      ftp.uu.net:/pub/archiving/zip/VMS/zip20x-vms.zip  (Vax/VMS exe)
  448.      ftp.uu.net:/pub/archiving/zip/AMIGA/unz51d3x.tar.Z(Amiga exe)
  449.      ftp.uu.net:/pub/archiving/zip/AMIGA/zip201x.zip   (Amiga exe)
  450.      ftp.uu.net:/pub/archiving/zip/OS2*/*              (OS/2 exe 16&32 bit)
  451.      ftp.uu.net:/pub/archiving/zip/zcrypt20.zip        (encryption source)
  452.          (Non US residents must get the crypt versions from garbo,see below)
  453.  
  454.      garbo.uwasa.fi:/unix/arcers/zip201.zip    (source)
  455.      garbo.uwasa.fi:/unix/arcers/unz50p1.tar.Z (source)
  456.      garbo.uwasa.fi:/pc/arcers/zip20x.zip      (MSDOS exe)
  457.      garbo.uwasa.fi:/pc/arcers/unz50p1.exe     (MSDOS exe)
  458.          garbo.uwasa.fi:/unix/arcers/zcrypt20.zip  (encryption source)
  459.  
  460.        for Macintosh:
  461.          mac.archive.umich.edu:/mac/util/compression/unzip2.01.cpt.hqx
  462.      mac.archive.umich.edu:/mac/util/compression/unzipmac5.0p1.cpt.hqx
  463.      mac.archive.umich.edu:/mac/util/compression/zipit1.2.cpt.hqx
  464.  
  465. .zoo: zoo 2.10 for MSDOS (algorithm copied from that of lha, see lha above)
  466.       Contact: Rahul Dhesi <dhesi@cirrus.com>
  467.      wuarchive.wustl.edu:/mirrors/msdos/zoo/zoo210.exe
  468.      garbo.uwasa.fi:/pc/arcers/zoo210.exe
  469.  
  470.       zoo 2.10 for Unix, VMS
  471.          oak.oakland.edu:/pub/misc/unix/zoo210.tar.Z
  472.      garbo.uwasa.fi:/unix/arcers/zoo210.tar.Z
  473.  
  474.       zoo for Mac
  475.       mac.archive.umich.edu:/mac/utilities/compressionapps/maczoo.sit.hqx
  476.  
  477.       zoo for Amiga
  478.     ftp.funet.fi:pub/amiga/utilities/archivers/Zoo-2.1.lha
  479.  
  480. .F: freeze for Unix (LZ77 with hashing, plus secondary dynamic Huffman
  481.          encoding)
  482.      wuarchive.wustl.edu:/usenet/comp.sources.misc/volume35/freeze/part0[1-3].Z
  483.      ftp.inria.fr:/system/arch-compr/freeze-2.5.tar.Z
  484.      Contact: Leonid A. Broukhis <leo@s514.ipmce.su>
  485.  
  486. .Y: yabba for Unix, VMS, ... (Y coding, a variant of LZ78)
  487.   wuarchive.wustl.edu:/usenet/comp.sources.unix/volume24/yabbawhap/part0[1-4].Z
  488.   ftp.inria.fr:/system/arch-compr/yabba.tar.Z
  489.   Contact: Dan Bernstein <djb@silverton.berkeley.edu>
  490.  
  491. .Z: compress for Unix ('the' LZW algorithm)
  492.       It is likely that your Unix system has 'compress' already. Otherwise:
  493.     wuarchive.wustl.edu:/packages/compression/compress-4.1.tar
  494.         (not in .Z format to avoid chicken and egg problem)
  495.  
  496.     compress for MSDOS
  497.     wuarchive.wustl.edu:/mirrors/msdos/compress/comp430[ds].zip
  498.     garbo.uwasa.fi:/pc/unix/comp430d.zip
  499.  
  500.     compress for Macintosh
  501.         sumex-aim.stanford.edu:/info-mac/util/maccompress-32.hqx
  502.  
  503.     compress for Amiga
  504.     ftp.funet.fi:pub/amiga/utilities/archivers/compress-4.1.lha
  505.  
  506.     compress for Vax/VMS
  507.     wuarchive.wustl.edu:/packages/compression/vax-vms/lzcomp.exe
  508.     wuarchive.wustl.edu:/packages/compression/vax-vms/lzdcmp.exe
  509.  
  510. ------------------------------------------------------------------------------
  511.  
  512. Subject: [3]  What is the latest PKZIP version?
  513.  
  514. The latest official version is 2.04g. Release 2.04c had serious bugs,
  515. corrected in 2.04e and 2.04g.
  516.  
  517. Be warned that there are countless bogus PKZIP 1.20, 2.0, 2.02,
  518. 3.05 and whatever scams floating around.  They usually are hacks of
  519. PKZIP 1.93A beta test version.  Some of them are trojans and / or
  520. carry computer virii.
  521.  
  522. Note about pkzip 2.06 from a PKware employee:
  523.  
  524.     Version 2.06 was released as an INTERNAL use only IBM version.
  525.     It is identical to 2.04G, but it has IBM names in the help
  526.     screens and such. That release is meant for IBM only.
  527.  
  528. ------------------------------------------------------------------------------
  529.  
  530. Subject: [4] What is an archiver?
  531.  
  532.  
  533. There is a distinction between archivers and other compression
  534. programs:
  535.  
  536. - an archiver takes several input files, compresses them and produces
  537.   a single archive file. Examples are arc, arj, lha, zip, zoo.
  538.  
  539. - other compression programs create one compressed file for each
  540.   input file. Examples are freeze, yabba, compress. Such programs
  541.   are often combined with tar to create compressed archives (see
  542.   question 50: "What is this tar compression program?").
  543.  
  544. ------------------------------------------------------------------------------
  545.  
  546. Subject: [5] What is the best general purpose compression program?
  547.  
  548.  
  549. The answer is: it depends. (You did not expect a definitive answer,
  550. did you?)
  551.  
  552. It depends whether you favor speed, compression ratio, a standard and
  553. widely used archive format, the number of features, etc...  Just as
  554. for text editors, personal taste plays an important role. compress has
  555. 4 options, arj 2.30 has about 130 options; different people like
  556. different programs. *Please* do not start or continue flame wars on
  557. such matters of taste.
  558.  
  559. The only objective comparisons are speed and compression ratio. Here
  560. is a short table comparing various programs on a 33Mhz Compaq 386.
  561. All programs have been run on Unix SVR4, except pkzip and arj which
  562. only run on MSDOS. (MSDOS benchmarks are available by ftp on
  563. oak.oakland.edu:/pub/msdos/info/arctst*.zip.)
  564.  
  565. *Please* do not post your own benchmarks made on your own files that
  566. nobody else can access. If you think that you must absolutely post yet
  567. another benchmark, make sure that your test files are available by
  568. anonymous ftp.
  569.  
  570. The programs compared here were chosen because they are the most
  571. popular or because they run on Unix and source is available.  For ftp
  572. information, see above. Three programs (hpack, comp-2 and ha) have
  573. been added because they achieve better compression (at the expense of
  574. speed) and one program (lzrw3-a) has been added because it favors
  575. speed at the expense of compression:
  576.  
  577. - comp-2 is in wuarchive.wustl.edu:/mirrors/msdos/ddjmag/ddj9102.zip
  578.   (inner zip file nelson.zip),
  579. - hpack is in wuarchive.wustl.edu:/mirrors/misc/unix/hpack75a.tar-z
  580.   and garbo.uwasa.fi:/unix/arcers/hpack78src.tar.Z
  581. - ha 0.98 is in garbo.uwasa.fi:/pc/arcers/ha098.zip
  582. - ftp.adelaide.edu.au:/pub/compression/lzrw3-a.c  [129.127.40.3]
  583.  
  584. The 14 files used in the comparison are from the standard Calgary
  585. Text Compression Corpus, available by ftp on ftp.cpsc.ucalgary.ca 
  586. [136.159.7.18] in /pub/text.compression.corpus/text.compression.corpus.tar.Z.
  587.  
  588. The whole corpus includes 18 files, but the 4 files paper[3-6] are
  589. generally omitted in benchmarks. It contains several kinds of file
  590. (ascii, binary, image, etc...) but has a bias towards large files.
  591. You may well get different ratings on the typical mix of files that
  592. you use daily, so keep in mind that the comparisons given below are
  593. only indicative.
  594.  
  595. The programs are ordered by decreasing total compressed size. For a
  596. fair comparison between archivers and other programs, this size is
  597. only the size of the compressed data, not the archive size.
  598.  
  599. The programs were run on an idle machine, so the elapsed time
  600. is significant and can be used to compare Unix and MSDOS programs.
  601.  
  602. [Note: I did not have time to run again all benchmarks with more
  603. recent versions of zip, freeze, arj and hpack. To be done for some
  604. future revision of this FAQ.]
  605.  
  606.        size     lzrw3a   compress    lharc    yabba     pkzip    freeze 
  607. version:                   4.0       1.02      1.0       1.10     2.3.5
  608. options:                                    -m300000                    
  609.        ------    -----    ------    ------    ------    ------   ------
  610. bib    111261    49040     46528     46502     40456     41354    41515 
  611. book1  768771   416131    332056    369479    306813    350560   344793 
  612. book2  610856   274371    250759    252540    229851    232589   230861 
  613. geo    102400    84214     77777     70955     76695     76172    68626 
  614. news   377109   191291    182121    166048    168287    157326   155783 
  615. obj1    21504    12647     14048     10748     13859     10546    10453 
  616. obj2   246814   108040    128659     90848    114323     90130    85500 
  617. paper1  53161    24522     25077     21748     22453     20041    20021 
  618. paper2  82199    39479     36161     35275     32733     32867    32693 
  619. pic    513216   111000     62215     61394     65377     63805    53291 
  620. progc   39611    17919     19143     15399     17064     14164    14143 
  621. progl   71646    24358     27148     18760     23512     17255    17064 
  622. progp   49379    16801     19209     12792     16617     11877    11686 
  623. trans   93695    30292     38240     28092     31300     23135    22861 
  624.     3,141,622  1,400,105 1,259,141 1,200,580 1,159,340 1,141,821 1,109,290
  625. real             0m35s     0m59s     5m03s     2m40s              5m27s
  626. user             0m25s     0m29s     4m29s     1m46s              4m58s
  627. sys              0m05s     0m10s     0m07s     0m18s              0m08s
  628. MSDOS:                                                   1m39s
  629.                         
  630.  
  631.          zoo       lha       arj      pkzip    zip      hpack   comp-2    ha
  632.         2.10    1.0(Unix)   2.30      2.04g    1.9      0.75a            0.98
  633.          ah    2.13(MSDOS)   -jm       -ex      -6                        a2
  634.        ------    ------    ------    ------  -------   ------   ------  ------
  635. bib     40742     40740     36090     35186    34950    35619    29840   26927
  636. book1  339076    339074    318382    313566   312619   306876   237380  235733
  637. book2  228444    228442    210521    207204   206306   208486   174085  163535
  638. geo     68576     68574     69209     68698    68418    58976    64590   59356
  639. news   155086    155084    146855    144954   144395   141608   128047  123335
  640. obj1    10312     10310     10333     10307    10295    10572    10819    9799
  641. obj2    84983     84981     82052     81213    81336    80806    85465   80381
  642. paper1  19678     19676     18710     18519    18525    18607    16895   15675
  643. paper2  32098     32096     30034     29566    29674    29825    25453   23956
  644. pic     52223     52221     53578     52777    55051    51778    55461   51639
  645. progc   13943     13941     13408     13363    13238    13475    12896   11795
  646. progl   16916     16914     16408     16148    16175    16586    17354   15298
  647. progp   11509     11507     11308     11214    11182    11647    11668   10498
  648. trans   22580     22578     20046     19808    18879    20506    21023   17927
  649.     1,096,166 1,096,138 1,036,934 1,019,451 1,021,043 1,005,367 890,976 845,854
  650. real    4m07s     6m03s                        1m49s   1h22m17s  27m05s
  651. user    3m47s     4m23s                        1m43s   1h20m46s  19m27s
  652. sys     0m04s     0m08s                        0m02s      0m12s   2m03s
  653. MSDOS:            1m49s     2m41s     1m43s                              14m43s
  654.  
  655. Notes:
  656.  
  657. - the compressed data for 'zoo ah' is always two bytes longer than for
  658.   lha. This is simply because both programs are derived from the same
  659.   source (ar002, written by Haruhiko Okumura, available by ftp in
  660.   wuarchive.wustl.edu:/mirrors/msdos/archivers/ar002.zip).
  661.  
  662. - hpack 0.75a gives slightly different results on SunOS. (To be checked
  663.   with latest version of hpack).
  664.  
  665. - the MSDOS versions are all optimized with assembler code and were run
  666.   on a RAM disk. So it is not surprising that they often go faster than
  667.   their Unix equivalent.
  668.  
  669. ------------------------------------------------------------------------------
  670.  
  671. Subject: [7] Which books should I read?
  672.  
  673.  
  674. [BWC 1989] Bell, T.C, Cleary, J.G. and Witten, I.H, "Text Compression",
  675.     Prentice-Hall 1989. ISBN: 0-13-911991-4. Price: approx. US$60
  676.     The reference on text data compression.
  677.  
  678. [Nel 1991] Mark Nelson, "The Data Compression Book"
  679.     M&T Books, Redwood City, CA, 1991.  ISBN 1-55851-216-0.
  680.     Price $36.95 including two 5" PC-compatible disks bearing
  681.     all the source code printed in the book.
  682.     A practical introduction to data compression.
  683.     The book is targeted at a person who is comfortable reading C code but
  684.     doesn't know anything about data compression.  Its stated goal is to get
  685.     you up to the point where you are competent to program standard
  686.     compression algorithms.
  687.  
  688. [Will 1990] Williams, R.  "Adaptive Data Compression", Kluwer Books, 1990.
  689.     ISBN: 0-7923-9085-7. Price: US$75.
  690.     Reviews the field of text data compression and then addresses the
  691.     problem of compressing rapidly changing data streams.
  692.  
  693. [Stor 1988] Storer, J.A.  "Data Compression: Methods and Theory", Computer
  694.     Science Press, Rockville, MD. ISBN: 0-88175-161-8.
  695.     A survey of various compression techniques, mainly statistical
  696.     non-arithmetic compression and LZSS compression.  Includes complete Pascal
  697.     code for a series of LZ78 variants.
  698.  
  699. [Stor 1992] Storer, J.A. "Image and Text Compression", Kluwer Academic
  700.     Publishers, 1992, ISBN 0-7923-9243-4
  701.  
  702. [ACG 1991] Advances in Speech Coding, edited by Atal, Cuperman, and Gersho,
  703.     Kluwer Academic Press, 1991.
  704.  
  705. [GG 1991] Vector Quantization and Signal Compression, by Gersho and Gray,
  706.     Kluwer Acad. Press, 1991, ISBN 0-7923-9181-0.
  707.  
  708. [CT 1991] Elements of Information Theory, by T.M.Cover and J.A.Thomas
  709.      John Wiley & Sons, 1991. ISBN 0-471-06259-6.
  710.  
  711. Review papers:
  712.  
  713. [BWC 1989] Bell, T.C, Witten, I.H, and Cleary, J.G.  "Modeling for Text
  714.     Compression", ACM Computing Surveys, Vol.21, No.4 (December 1989), p.557
  715.     A good general overview of compression techniques (as well as modeling for
  716.     text compression); the condensed version of "Text Compression".
  717.  
  718. [Lele 1987] Lelewer, D.A, and Hirschberg, D.S.  "Data Compression", ACM
  719.     Computing Surveys, Vol.19, No.3 (September 1987), p.261.
  720.     A survey of data compression techniques which concentrates on Huffman
  721.     compression and makes only passing mention of other techniques.
  722.  
  723.  
  724. ------------------------------------------------------------------------------
  725.  
  726. Subject: [8] What about patents on data compression algorithms?
  727.  
  728.  
  729. [Note: the appropriate group for discussing software patents is
  730. comp.patents (or misc.legal.computing), not comp.compression.]
  731.  
  732. All patents mentioned here are US patents, and thus probably
  733. not applicable outside the US. See item 70, "Introduction to data
  734. compression" for the meaning of LZ77, LZ78 or LZW.
  735.  
  736.  
  737. (a) Run length encoding
  738.  
  739. - Tsukiyama has two patents on run length encoding: 4,586,027 and 4,872,009
  740.   granted in 1986 and 1989 respectively. The first one covers run length
  741.   encoding in its most primitive form: a length byte followed by the
  742.   repeated byte. The second patent covers the 'invention' of limiting the
  743.   run length to 16 bytes and thus the encoding of the length on 4 bits.
  744.   Here is the start of claim 1 of patent 4,872,009, just for pleasure:
  745.  
  746.     1. A method of transforming an input data string comprising a plurality
  747.     of data bytes, said plurality including portions of a plurality of
  748.     consecutive data bytes identical to one another, wherein said data
  749.     bytes may be of a plurality of types, each type representing different
  750.     information, said method comprising the steps of: [...]
  751.  
  752. - O'Brien has patented (4,988,998) run length encoding followed by LZ77.
  753.  
  754.  
  755. (b) LZ77
  756.  
  757. - Waterworth patented (4,701,745) the algorithm now known as LZRW1,
  758.   because Ross Williams reinvented it later and posted it on
  759.   comp.compression on April 22, 1991. (See item 5 for the ftp site
  760.   with all LZRW derivatives.) The *same* algorithm has later been
  761.   patented by Gibson & Graybill (see below). The patent office failed
  762.   to recognize that the same algorithm was patented twice, even though
  763.   the wording used in the two patents is very similar.
  764.  
  765.   The Waterworth patent is now owned by Stac Inc, and used as the basis
  766.   of a lawsuit against Microsoft, concerning the compression feature
  767.   of MSDOS 6.0.
  768.  
  769. - Fiala and Greene obtained in 1990 a patent (4,906,991) on all
  770.   implementations of LZ77 using a tree data structure. Claim 1 of the
  771.   patent is much broader than the algorithms published by Fiala and
  772.   Greene in Comm.ACM, April 89. The patent covers the algorithm
  773.   published by Rodeh and Pratt in 1981 (J. of the ACM, vol 28, no 1,
  774.   pp 16-24).  It also covers the algorithm previously patented by
  775.   Eastman-Lempel-Ziv (4,464,650), and the algorithms used in lharc,
  776.   lha and zoo.
  777.  
  778. - Notenboom (from Microsoft) 4,955,066 uses three levels of
  779.   compression, starting with run length encoding.
  780.  
  781. - The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm
  782.   previously patented by Waterworth and reinvented by Ross Williams.
  783.   Claims 4 and 12 are very general and could be interpreted as
  784.   applying to any LZ algorithm using hashing (including all variants
  785.   of LZ78):
  786.  
  787.      4. A compression method for compressing a stream of input data into
  788.      a compressed stream of output data based on a minimum number of
  789.      characters in each input data string to be compressed, said
  790.      compression method comprising the creation of a hash table, hashing
  791.      each occurrence of a string of input data and subsequently searching
  792.      for identical strings of input data and if such an identical string
  793.      of input data is located whose string size is at least equal to the
  794.      minimum compression size selected, compressing the second and all
  795.      subsequent occurrences of such identical string of data, if a string
  796.      of data is located which does not match to a previously compressed
  797.      string of data, storing such data as uncompressed data, and for each
  798.      input strings after each hash is used to find a possible previous
  799.      match location of the string, the location of the string is stored
  800.      in the hash table, thereby using the previously processed data to
  801.      act as a compression dictionary.
  802.  
  803.   Claim 12 is identical, with 'method' replaced with 'apparatus'.  Since
  804.   the 'minimal compression size' can be as small as 2, the claim could
  805.   cover any dictionary technique of the LZ family. However the text of the
  806.   patent and the other claims make clear that the patent should cover the
  807.   LZRW1 algorithm only. (In any case the Gibson & Graybill patent is likely
  808.   to be invalid because of the prior art in the Waterworth patent.)
  809.  
  810. - Phil Katz, author of pkzip, also has a patent on LZ77 (5,051,745)
  811.   but the claims only apply to sorted hash tables, and when the hash
  812.   table is substantially smaller than the window size.
  813.  
  814. - IBM patented (5,001,478) the idea of combining a history buffer (the
  815.   LZ77 technique) and a lexicon (as in LZ78).
  816.  
  817. - Stac Inc patented (5,016,009 and 5,126,739) yet another variation of LZ77
  818.   with hashing. The '009 patent is used in the lawsuit against Microsoft
  819.   (see above). Stac also has patents on LZ77 with parallel lookup in
  820.   hardware (4,841,092 and 5,003,307).
  821.  
  822. - Robert Jung, author of 'arj', has been granted patent 5,140,321
  823.   for one variation of LZ77 with hashing.  This patent covers the LZRW3-A
  824.   algorithm, also previously discovered by Ross Williams. LZRW3-A was posted
  825.   on comp.compression on July 15, 1991. The patent was filed two months later
  826.   on Sept 4, 1991. (The US patent system allows this because of the
  827.   'invention date' rule.)
  828.  
  829. - Chambers 5,155,484 is yet another variation of LZ77 with hashing.
  830.   The hash function is just the juxtaposition of two input bytes,
  831.   this is the 'invention' being patented. The hash table is named
  832.   'direct lookup table'.
  833.  
  834.  
  835. (c) LZ78
  836.  
  837. - One form of the original LZ78 algorithm was patented (4,464,650) by
  838.   its authors Lempel, Ziv, Cohn and Eastman.
  839.  
  840. - The LZW algorithm used in 'compress' is patented by IBM (4,814,746)
  841.   and Unisys (4,558,302). It is also used in the V.42bis compression
  842.   standard (see question 11 on V.42bis below) and in Postscript Level 2.
  843.   (Unisys sells the license to modem manufacturers for a onetime
  844.   $25,000 fee.) The IBM patent application was filed three weeks
  845.   before that of Unisys, but the US patent office failed to recognize
  846.   that they covered the same algorithm. (The IBM patent is more
  847.   general, but its claim 7 is exactly LZW.)
  848.  
  849. - AP coding is patented by Storer (4,876,541). (Get the yabba package
  850.   for source code, see question 2 above, file type .Y)
  851.  
  852.  
  853. (d) arithmetic coding
  854.  
  855. - IBM holds many patents on arithmetic coding (4,286,256 4,295,125
  856.   4,463,342 4,467,317 4,633,490 4,652,856 4,891,643 4,905,297 4,935,882).
  857.   It has patented in particular the Q-coder implementation of arithmetic
  858.   coding.  The arithmetic coding option of the JPEG standard requires
  859.   use of the patented algorithm.  No JPEG-compatible method is
  860.   possible without infringing the patent, because what IBM actually
  861.   claims rights to is the underlying probability model (the heart of
  862.   an arithmetic coder). (See the JPEG FAQ for details.)
  863.  
  864.   AT&T has 3 patents on arithmetic coding (4,973,961, 5,023,611, 5,025,258).
  865.  
  866.  
  867. As can be seen from the above list, some of the most popular compression
  868. programs (compress, pkzip, zoo, lha, arj) are now covered by patents.
  869. (This says nothing about the validity of these patents.)
  870.  
  871. Here are some references on data compression patents. A number of them are
  872. taken from the list prep.ai.mit.edu:/pub/lpf/patent-list.
  873.  
  874. 3,914,586
  875. Data compression method and apparatus
  876. filed 10/25/73, granted 10/21/75
  877. General Motors Corporation, Detroit MI
  878. Duane E. McIntosh, Santa Ynez CA
  879. Data compression apparatus is disclosed is operable in either a bit
  880. pair coding mode of a word coding mode depending on the degree of
  881. redundancy of the data to be encoded.
  882.  
  883. 3,976,844
  884. Data communication system for transmitting data in compressed form
  885. filed Apr. 4, 1975, granted Aug. 24, 1976
  886. inventor  Bernard K. Betz, assignee Honeywell Information Systems, Inc.
  887. [encode differences with previous line]
  888.  
  889. 4,021,782
  890. Data compaction system and apparatus
  891. inventor Hoerning
  892. filed 04/30/1975, granted 05/03/1977
  893. [A primitive form of LZ77 with implicit offsets (compare with previous record)]
  894.  
  895. 4,054,951
  896. Data expansion apparatus
  897. inventor R.D. Jackson, assignee IBM
  898. filed Jun. 30, 1976, granted Oct. 18, 1977
  899. [Covers only decompression of data compressed with a variant of LZ77.]
  900.  
  901. 4,087,788
  902. Data compression system
  903. filed 1/14/77, granted 5/2/78
  904. NCR Canada LTD - NCR Canada Ltee, Mississauga CA
  905. Brian J. Johannesson, Waterloo CA
  906. A data compression system is disclosed in which the left hand boundary
  907. of a character is developed in the form of a sequence of Freeman
  908. direction codes, the codes being stored in digital form within a
  909. processor.
  910.  
  911. 4,286,256
  912. Method and means for arithmetic coding using a reduced number of operations.
  913. granted Aug 25, 1981
  914. assignee IBM
  915.  
  916. 4,295,125
  917. A method and means for pipeline decoding of the high to low order pairwise
  918. combined digits of a decodable set of relatively shifted finite number of
  919. strings
  920. granted Oct 13, 1981
  921. assignee IBM
  922.  
  923. 4,412,306
  924. System for minimizing space requirements for storage and transmission of
  925. digital signals
  926. filed May 14, 1981, granted Oct. 25, 1983
  927. inventor  Edward W. Moll
  928.  
  929. 4,463,342
  930. A method and means for carry-over control in a high order to low order
  931. combining of digits of a decodable set of relatively shifted finite number
  932. strings.
  933. granted Jul 31, 1984
  934. assignee IBM
  935.  
  936. 4,491,934
  937. Data compression process
  938. filed May 12, 1982, granted Jan. 1, 1985
  939. inventor  Karl E. Heinz
  940.  
  941. 4,464,650
  942. Apparatus and method for compressing data signals and restoring the
  943. compressed data signals
  944. inventors Lempel, Ziv, Cohn, Eastman
  945. assignees Sperry Corporation and At&T Bell Laboratories
  946. filed 8/10/81, granted 8/7/84
  947. A compressor parses the input data stream into segments where each
  948. segment comprises a prefix and the next symbol in the data stream
  949. following the prefix.
  950.  
  951. 4,467,317
  952. High-speed arithmetic compression using using concurrent value updating.
  953. granted Aug 21, 1984
  954. assignee IBM
  955.  
  956. 4,494,108
  957. Adaptive source modeling for data file compression within bounded memory
  958. filed Jun. 5, 1984, granted Jan. 15, 1985
  959. invntors Glen G. Langdon, Jorma J. Rissanen
  960. assignee IBM
  961. order 1 Markov modeling
  962.  
  963. 4,558,302
  964. High speed data compression and decompression apparatus and method
  965. inventor Welch
  966. assignee Sperry Corporation (now Unisys)
  967. filed 6/20/83, granted 12/10/85
  968. The text for this patent can be ftped from rusmv1.rus.uni-stuttgart.de
  969. (129.69.1.12) in /info/comp.patents/US4558302.Z.
  970.  
  971. 4,560,976
  972. Data compression
  973. filed 6/5/84, granted 12/24/85
  974. Codex Corporation, Mansfield MA
  975. Steven G. Finn, Framingham, MA
  976. A stream of source characters, which occur with varying relative
  977. frequencies, is encoded into a compressed stream of codewords, each
  978. having one, two or three subwords, by ranking the source characters by
  979. their current frequency of appearance, encoding the source characters
  980. having ranks no higher than a first number as one subword codewords,
  981. source characters having ranks higher than the first number but no
  982. higher than a second number as two subword codewords, and the
  983. remaining source characters as three subword codewords.
  984.  
  985. 4,586,027
  986. Method and system for data compression and restoration
  987. inventor Tsukimaya et al.
  988. assignee Hitachi
  989. filed 08/07/84, granted 04/29/86
  990. patents run length encoding
  991.  
  992. 4,597,057
  993. System for compressed storate of 8-bit ascii bytes using coded strings
  994. of 4-bit nibbles.
  995. inventor Snow, assignee System Development corporation.
  996. filed 12/31/1981, granted 06/24/1986.
  997. Compression using static dictionary of common words, prefixes and suffixes.
  998.  
  999. 4,612,532
  1000. Data compression apparatus and method
  1001. inventor Bacon, assignee Telebyte Corportion
  1002. filed Jun. 19, 1984, granted Sep. 16, 1986
  1003. [Uses followsets as in the pkzip 0.92 'reduce' algorithm, but the
  1004. followsets are dynamically updated. This is in effect a sort of order-1
  1005. Markov modeling.]
  1006.  
  1007. 4,622,545
  1008. Method and apparatus for image compression and Manipulation
  1009. inventor William D. Atkinson
  1010. assignee Apple computer Inc.
  1011. filed 9/30/82
  1012. granted 11/11/86
  1013.  
  1014. 4,633,490
  1015. Symmetrical adaptive data compression/decompression system.
  1016. granted Dec 30, 1985
  1017. assignee IBM
  1018.  
  1019. 4,652,856
  1020. A multiplication-free multi-alphabet arithmetic code.
  1021. granted Feb  4, 1986
  1022. assignee IBM
  1023.  
  1024. 4,667,649
  1025. Data receiving apparatus
  1026. filed 4/18/84, granted 6/30/87
  1027. inventors Kunishi et al.
  1028. assignee Canon Kabushiki Kaisha, Tokyo Japan
  1029. compression of Fax images.
  1030.  
  1031. 4,682,150
  1032. Data compression method and apparatus
  1033. inventors Mathes and Protheroe, 
  1034. assignee NCR Corporation, Dayton OH
  1035. A system and apparatus for compressing redundant and nonredundant
  1036. binary data generated as part of an operation of a time and attendance
  1037. terminal in which the data represents the time an employee is present
  1038. during working hours.
  1039.  
  1040. 4,701,745
  1041. Data compression system
  1042. inventor Waterworth John R
  1043. assignee Ferranti PLC GB, patent rights now acquired by Stac Inc.
  1044. filed 03/03/1986 (03/06/1985 in GB), granted 10/20/1987
  1045. Algorithm now known as LZRW1 (see above)
  1046. I claim:
  1047. 1. A data compression system comprising an input store for receiving
  1048. and storing a plurality of bytes of uncompressed data from an outside
  1049. source, and data processing means for processing successive bytes of
  1050. data from the input store;
  1051. the data processing means including circuit means operable to check
  1052. whether a sequence of successive bytes to be processed identical with
  1053. a sequence of bytes already processed, and including hash generating
  1054. means responsive to the application of a predetermined number of
  1055. bytes in sequence to derive a hash code appropriate to those bytes, a
  1056. temporary store in which the hash code may represent the address of a
  1057. storage location, and a pointer counter operable to store in the
  1058. temporary store at said address a pointer indicative of the position
  1059. in the input store of one of the predetermined number of bytes;
  1060. output means operable to apply to a transfer medium each byte of data
  1061. not forming part of such an identical sequence; and
  1062. encoding means responsive to the identification of such a sequence to
  1063. apply to the transfer medium an identification signal which identifies
  1064. both the location in the input store of the previous occurrence of the
  1065. sequence of bytes and the number of bytes contained in the sequence.
  1066.  
  1067. 4,730,348
  1068. Adaptive data compression system
  1069. inventor MacCrisken, assignee Adaptive Computer Technologies
  1070. filed Sep. 19, 1986, granted Mar. 8, 1988
  1071. [order-1 Markov modeling + Huffman coding + LZ77]
  1072.  
  1073. 4,758,899
  1074. Data compression control device
  1075. inventor Tsukiyama, assignee Hitachi
  1076. filed 11/20/1985, granted 07/19/1988
  1077. Limits compression to ensure that tape drive stays busy.
  1078.  
  1079. 4,809,350
  1080. Data compression system
  1081. filed Jan. 30, 1987, granted Feb. 28, 1989
  1082. inventor Yair Shimoni & Ron Niv
  1083. assignee Elscint Ltd., Haifa, Israel
  1084. [Image compression via variable length encoding of differences with
  1085. predicted data.]
  1086.  
  1087. 4,814,746
  1088. Data compression method
  1089. inventors Victor S. Miller, Mark N. Wegman
  1090. assignee IBM
  1091. filed 8/11/86, granted 3/21/89
  1092. A previous application was filed on 6/1/83, three weeks before the
  1093. application by Welch (4,558,302)
  1094. Communications between a Host Computing System and a number of remote
  1095. terminals is enhanced by a data compression method which modifies the
  1096. data compression method of Lempel and Ziv by addition of new character
  1097. and new string extensions to improve the compression ratio, and
  1098. deletion of a least recently used routine to limit the encoding tables
  1099. to a fixed size to significantly improve data transmission efficiency.
  1100.  
  1101. 4,841,092
  1102. continued in 5,003,307
  1103.  
  1104. 4,853,696
  1105. Code converter for data compression/decompression
  1106. filed 4/13/87, granted 8/1/89
  1107. inventor Amar Mukherjee, Maitland FL
  1108. assignee University of Central Florida, Orlando FL
  1109. Another hardware Huffman encoder:
  1110. A code converter has a network of logic circuits connected in reverse
  1111. binary tree fashion with logic paths between leaf nodes and a common
  1112. root node.
  1113.  
  1114. 4,872,009
  1115. Method and apparatus for data compression and restoration
  1116. inventor Tsukimaya et al.
  1117. assignee Hitachi
  1118. filed 12/07/87, granted 10/03/89
  1119. This patent on run length encoding covers the 'invention' of limiting
  1120. the run length to 16 bytes and thus the encoding of the length on 4 bits.
  1121.  
  1122. 4,876,541
  1123. Stem [sic] for dynamically compressing and decompressing electronic data
  1124. filed 10/15/87, granted 10/24/89
  1125. inventor James A. Storer
  1126. assignee Data Compression Corporation
  1127. A data compression system for encoding and decoding textual data,
  1128. including an encoder for encoding the data and for a decoder for
  1129. decoding the encoded data.
  1130.  
  1131. 4,891,643
  1132. Arithmetic coding data compression/de-compression by selectively
  1133. employed, diverse arithmetic encoders and decoders.
  1134. granted Jan  2, 1990
  1135. assignee IBM
  1136.  
  1137. 4,905,297
  1138. granted Feb 27, 1990
  1139. assignee IBM
  1140. Arithmetic coding encoder and decoder system.
  1141.  
  1142. 4,906,991
  1143. Textual substitution data compression with finite length search window
  1144. filed 4/29/1988, granted 3/6/1990
  1145. inventors Fiala,E.R., and Greene,D.H.
  1146. assignee Xerox Corporation
  1147.  
  1148. 4,935,882
  1149. Probability adaptation for arithmetic coders.
  1150. granted Jun 19, 1990
  1151. assignee IBM
  1152.  
  1153. 4,941,193
  1154. Barnsley, fractal compression.
  1155.  
  1156. 4,943,869
  1157. Compression Method for Dot Image Data
  1158. filed 1988-05-04, granted 1990-07-24
  1159. assignee Fuji Photo Film Co.
  1160. Lossy and lossless image compression schemes.
  1161.  
  1162. 4,955,066
  1163. Compressing and Decompressing Text Files
  1164. filed  10/13/89, granted 09/04/90
  1165. inventor Notenboom, L.A.
  1166. assignee Microsoft
  1167. Now extended as 5,109,433
  1168. [Noted in signon screen of Word 5.5 and on the outside of the MS-DOS 5.0
  1169. Upgrade.]
  1170. A method of compressing a text file in digital form is disclosed.
  1171. A full text file having characters formed into phrases is provided by an
  1172. author.  The characters are digitally represented by bytes.  A first pass
  1173. compression is sequentially followed by a second pass compression of the
  1174. text which has previously been compressed.  A third or fourth level of
  1175. compression is serially performed on the compressed text.  For example, in
  1176. a first pass, the text is run-length compressed.  In a second pass, the
  1177. compressed text is further compressed with key phrase compression.  In a
  1178. third pass, the compressed text is further compressed with Huffman
  1179. compression.  The compressed text is stored in a text file having a Huffman
  1180. decode tree, a key phrase table, and a topic index.  The data is
  1181. decompressed in a single pass and provided one line at a time as an output.
  1182. Sequential compressing of the text minimizes the storage space required for
  1183. the file.  Decompressing of the text is performed in a single pass.  As a
  1184. complete line is decompressed, it is output rapidly, providing full text to
  1185. the user.
  1186.  
  1187. 4,973,961
  1188. Method and apparatus for carry-over control in arithmetic coding.
  1189. granted Nov 27, 1990
  1190. assignee AT&T
  1191.  
  1192. 4,988,998
  1193. Data compression system for successively applying at least two data
  1194. compression methods to an input data stream.
  1195. inventor O'Brien
  1196. assignee Storage Technology Corporation, Louisville, Colorado
  1197. filed Sep 5, 1989, granted Jan 29, 1991.
  1198. Run length encoding followed by LZ77.
  1199.  
  1200. 5,001,478
  1201. Method of Encoding Compressed Data
  1202. filed 12/28/89, granted 03/19/91
  1203. inventor Michael E. Nagy
  1204. assignee IBM
  1205. 1. A method of encoding a compressed data stream made up of a sequence of
  1206. literal references, lexicon references and history references, which
  1207. comprises the steps of:
  1208. assigning to each literal reference a literal identifier;
  1209. assigning to each history reference a history identifier;
  1210. assigning to each lexicon reference a lexicon identifier;
  1211. and emitting a data stream with said identifiers assigned to said references.
  1212. Gordon Irlam <gordoni@cs.adelaide.edu.au> says:
  1213. The invention can probably be best understood by considering the
  1214. decompressor.  It consists of a history buffer, and a lexicon buffer, both
  1215. of which are initially empty.  The history buffer contains the last n
  1216. symbols emitted.  Whenever a history buffer reference is to be output the
  1217. string so referenced is subsequently moved to the lexicon buffer for future
  1218. reference.  Thus the history buffer keeps track of strings that may be
  1219. repeated on a very short term basis, while the lexicon buffer stores items
  1220. for a longer time.  Furthermore a history reference involves specifying
  1221. both the offset and length within the history buffer, whereas a lexicon
  1222. reference simply specifies a number denoting the string.  Both buffers have
  1223. a finite size.
  1224.  
  1225. 5,003,307
  1226. Data compression apparatus with shift register search means
  1227. filed Oct. 6, 1989, granted Mar. 26, 1991
  1228. inventors George Glen A, Ivey Glen E, Whiting Douglas L
  1229. assignee Stac Inc
  1230. continuation of 4,841,092
  1231.  
  1232. 5,016,009
  1233. Data compression apparatus and method
  1234. filed 01/13/1989, granted 05/14/1991
  1235. inventors George Glen A, Ivey Glen E, Whiting Douglas L
  1236. assignee Stac Inc
  1237. LZ77 with offset hash table (extended in 5,126,739)
  1238.  
  1239. 5,023,611
  1240. Entropy encoder/decoder including a context extractor.
  1241. granted Jun 11, 1991
  1242. assignee AT&T
  1243.  
  1244. 5,025,258
  1245. Adaptive probability estimator for entropy encoder/decoder.
  1246. granted Jun 18, 1991
  1247. assignee AT&T
  1248.  
  1249. 5,049,881
  1250. Apparatus and method for very high data rate-compression incorporating
  1251. lossless data compression and expansion utilizing a hashing technique
  1252. inventors Dean K. Gibson, Mark D. Graybill
  1253. assignee Intersecting Concepts, Inc.
  1254. filed 6/18/90, granted 9/17/91
  1255. [covers lzrw1, almost identical with Waterworth 4,701,745]
  1256.  
  1257. 5,051,745
  1258. String searcher, and compressor using same
  1259. filed  8/21/90, granted 9/24/91
  1260. inventor  Phillip W. Katz (author of pkzip)
  1261. In the string search method and apparatus pointers to the string to be
  1262. searched are indexed via a hashing function and organized according to the
  1263. hashing values of the string elements pointed to. The hashing function is
  1264. also run on the string desired to be found, and the resulting hashing value
  1265. is used to access the index. If the resulting hashing value is not in the
  1266. index, it is known that the target string does not appear in the string
  1267. being searched. Otherwise the index is used to determine the pointers which
  1268. correspond to the target hashing value, these pointers pointing to likely
  1269. candidates for matching the target string. The pointers are then used to
  1270. sequentially compare each of the locations in the string being searched to
  1271. the target string, to determine whether each location contains a match to
  1272. the target string.
  1273. In the method and apparatus for compressing a stream of data symbols, a
  1274. fixed length search window, comprising a predetermined contiguous portion
  1275. of the symbol stream, is selected as the string to be searched by the
  1276. string searcher. If a string to be compressed is found in the symbol
  1277. stream, a code is output designating the location within the search window
  1278. of the matching string and the length of the matching string.
  1279.  
  1280. 5,065,447
  1281. Barnsley, fractal compression
  1282.  
  1283. 5,109,433
  1284. Compressing and decompressing text files
  1285. inventor Notenboom
  1286. assignee Microsoft
  1287. extension of 4,955,066
  1288.  
  1289. 5,126,739
  1290. Data Compression Apparatus and Method
  1291. filed Nov. 27, 1990, granted June 30, 1992.
  1292. inventor Whiting et. al
  1293. assignee Stac Inc
  1294. LZ77 with offset hash table (extension of 5,016,009)
  1295.  
  1296. 5,140,321
  1297. Data compression/decompression method and apparatus
  1298. filed 9/4/91, granted 8/18/92
  1299. inventor Robert Jung
  1300. assignee Prime Computer
  1301.  
  1302. 5,155,484
  1303. Fast data compressor with direct lookup table indexing into history buffer
  1304. filed 9/13/1991, granted 10/13/1992
  1305. inventor Chambers, IV, Lloyd L., Menlo Park, California
  1306. assignee Salient Software, Inc., Palo Alto, California (02)
  1307. Uses a 64K hash table indexed by the first two characters of
  1308. the input string. Includes several claims on the LZ77 file format
  1309. (literal or offset,length).
  1310.  
  1311. 5,179,378
  1312. file Jul. 30, 1991, granted Jan. 12, 1993
  1313. inventor Ranganathan
  1314. assignee University of South Florida
  1315. Method and apparatus for the compression and decompression of data
  1316. using Lempel-Ziv based techniques.
  1317. [This covers LZ77 hardware compression with a systolic array of
  1318. processors working in parallel.]
  1319.  
  1320. Japan 2-46275
  1321. Coding system
  1322. granted Feb 26, 1990
  1323. [Patents one form of arithmetic coding.]
  1324.  
  1325. ------------------------------------------------------------------------------
  1326.  
  1327. Subject: [9]  The WEB 16:1 compressor.
  1328.  
  1329.  
  1330. [WARNING: this topic has generated the greatest volume of news in the
  1331. history of comp.compression. Read this before posting on this subject.]
  1332.  
  1333. [WARNING 2: it is quite possible that the story is repeating itself
  1334. with a compressor called MINC by Premier Research Corporation, Ltd.
  1335. They claim a breakthrough in lossless data compression using a recursive
  1336. method, that is, applying the compressor to the compressed output of
  1337. the previous run.]
  1338.  
  1339. [WARNING 3: the OWS program, which also claims incredible compression
  1340. ratios, is a hoax. It just remembers the clusters which contained
  1341. the data. The data can be recovered only if those clusters are not
  1342. used again for another file. Needless to say, never trust such a
  1343. lossy program.]
  1344.  
  1345. (a) What the press says
  1346.  
  1347. April 20, 1992  Byte Week Vol 4. No. 25:
  1348.  
  1349.    "In an announcement that has generated high interest - and more than a
  1350.    bit of skepticism - WEB Technologies (Smyrna, GA) says it has
  1351.    developed a utility that will compress files of greater than 64KB in
  1352.    size to about 1/16th their original length.  Furthermore, WEB says its
  1353.    DataFiles/16 program can shrink files it has already compressed."
  1354.    [...]
  1355.    "A week after our preliminary test, WEB showed us the program successfully
  1356.    compressing a file without losing any data.  But we have not been able
  1357.    to test this latest beta release ourselves."
  1358.    [...]
  1359.    "WEB, in fact, says that virtually any amount of data can be squeezed 
  1360.    to under 1024 bytes by using DataFiles/16 to compress its own output
  1361.    multiple times."
  1362.  
  1363. June 1992 Byte, Vol 17 No 6:
  1364.  
  1365.    [...] According to Earl Bradley, WEB Technologies' vice president of
  1366.    sales and marketing, the compression algorithm used by DataFiles/16
  1367.    is not subject to the laws of information theory. [...]
  1368.  
  1369.  
  1370. (b) First details, by John Wallace <buckeye@spf.trw.com>:
  1371.  
  1372. I called WEB at (404)514-8000 and they sent me some product
  1373. literature as well as chatting for a few minutes with me on the phone.
  1374. Their product is called DataFiles/16, and their claims for it are
  1375. roughly those heard on the net.
  1376.  
  1377. According to their flier:
  1378.  
  1379. "DataFiles/16 will compress all types of binary files to approximately
  1380. one-sixteenth of their original size ... regardless of the type of
  1381. file (word processing document, spreadsheet file, image file,
  1382. executable file, etc.), NO DATA WILL BE LOST by DataFiles/16."
  1383. (Their capitalizations; 16:1 compression only promised for files >64K
  1384. bytes in length.)
  1385.  
  1386. "Performed on a 386/25 machine, the program can complete a
  1387. compression/decompression cycle on one megabyte of data in less than
  1388. thirty seconds"
  1389.  
  1390. "The compressed output file created by DataFiles/16 can be used as the 
  1391. input file to subsequent executions of the program.  This feature of 
  1392. the utility is known as recursive or iterative compression, and will 
  1393. enable you to compress your data files to a tiny fraction of the 
  1394. original size.  In fact, virtually any amount of computer data can 
  1395. be compressed to under 1024 bytes using DataFiles/16 to compress its 
  1396. own output files muliple times.  Then, by repeating in reverse the 
  1397. steps taken to perform the recusive compression, all original data 
  1398. can be decompressed to its original form without the loss of a single 
  1399. bit."
  1400.  
  1401. Their flier also claims: 
  1402.  
  1403. "Constant levels of compression across ALL TYPES of FILES"
  1404. "Convenient, single floppy DATA TRANSPORTATION"
  1405.  
  1406. From my telephone conversation, I was was assured that this is an
  1407. actual compression program.  Decompression is done by using only the 
  1408. data in the compressed file; there are no hidden or extra files.
  1409.  
  1410.  
  1411. (c) More information, by Rafael Ramirez <rafael.ramirez@channel1.com>:
  1412.  
  1413.    Today (Tuesday, 28th) I got a call from Earl Bradley of Web
  1414. who now says that they have put off releasing a software version of
  1415. the algorithm because they are close to signing a major contract with
  1416. a big company to put the algorithm in silicon.  He said he could not
  1417. name the company due to non-disclosure agreements, but that they had
  1418. run extensive independent tests of their own and verified that the
  1419. algorithm works. [...]
  1420.  
  1421. He said the algorithm is so simple that he doesn't want anybody
  1422. getting their hands on it and copying it even though he said they
  1423. have filed a patent on it. [...] Mr. Bradley said the silicon version
  1424. would hold up much better to patent enforcement and be harder to copy.
  1425.  
  1426.    He claimed that the algorithm takes up about 4K of code, uses only
  1427. integer math, and the current software implementation only uses a 65K
  1428. buffer.  He said the silicon version would likely use a parallel
  1429. version and work in real-time. [...]
  1430.  
  1431.  
  1432. (d) The impossiblity proofs.
  1433.  
  1434. It is impossible for a given program to compress without loss *all*
  1435. files greater than a certain size by at least one bit. This can be
  1436. proven by a simple counting argument. (Many other proofs have been
  1437. posted on comp.compression, *please* do not post yet another one.)
  1438.  
  1439. Assume that the program can compress without loss all files of size >= N
  1440. bits.  Compress with this program all the 2^N files which have
  1441. exactly N bits.  All compressed files have at most N-1 bits, so there
  1442. are at most (2^N)-1 different compressed files [2^(N-1) files of size
  1443. N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at
  1444. least two different input files must compress to the same output file.
  1445. Hence the compression program cannot be lossless. (Stronger results
  1446. about the number of incompressible files can be obtained, but the
  1447. proofs are a little more complex.)
  1448.  
  1449. This argument applies of course to WEB's case (take N = 64K*8 bits).
  1450. Note that no assumption is made about the compression algorithm.
  1451. The proof applies to *any* algorithm, including those using an
  1452. external dictionary, or repeated application of another algorithm,
  1453. or combination of different algorithms, or representation of the
  1454. data as formulas, etc... All schemes are subject to the counting argument.
  1455. There is no need to use information theory to provide a proof, just
  1456. basic mathematics.
  1457.  
  1458. This assumes of course that the information available to the decompressor
  1459. is only the bit sequence of the compressed data. If external information
  1460. such as a file name or a number of iterations is necessary to decompress
  1461. the data, the bits providing the extra information must be included in
  1462. the bit count of the compressed data. (Otherwise, it would be sufficient
  1463. to consider any input data as a number, use this as the iteration
  1464. count or file name, and pretend that the compressed size is zero.)
  1465. For an example of storing information in the file name, see the program
  1466. lmfjyh in the 1993 International Obfuscated C Code Contest, available
  1467. on all comp.sources.misc archives (Volume 39, Issue 104).
  1468.  
  1469. [See also question 73 "What is the theoretical compression limit?" in
  1470. part 2 of this FAQ.]
  1471.  
  1472.  
  1473. (e) No software version
  1474.  
  1475. Appeared on BIX, reposted by Bruce Hoult <Bruce.Hoult@actrix.gen.nz>:
  1476.  
  1477. tojerry/chaos #673, from abailey, 562 chars, Tue Jun 16 20:40:34 1992
  1478. Comment(s). 
  1479. ----------
  1480. TITLE: WEB Technology
  1481. I promised everyone a report when I finally got the poop on WEB's
  1482. 16:1 data compression. After talking back and forth for a year
  1483. and being put off for the past month by un-returned phone calls,
  1484. I finally got hold of Marc Spindler who is their sales manager.
  1485.  
  1486. _No_ software product is forth coming, period!
  1487.  
  1488. He began talking about hardware they are designing for delivery
  1489. at the end of the year. [...]
  1490.  
  1491.  
  1492. (f) Product cancelled
  1493.  
  1494. Posted by John Toebes <toebes@bnr.ca> on Aug 10th, 1992:
  1495.  
  1496. [Long story omitted, confirming the reports made above about the
  1497. original WEB claims.]
  1498.  
  1499. 10JUL92 - Called to Check Status.  Was told that testing had uncovered a
  1500.           new problem where 'four numbers in a matrix were the same
  1501.           value' and that the programmers were off attempting to code a
  1502.           preprocessor to eliminate this rare case.  I indicated that he
  1503.           had told me this story before.  He told me that the
  1504.           programmers were still working on the problem.
  1505.  
  1506. 31JUL92 - Final Call to Check Status.  Called Earl in the morning and
  1507.           was told that he still had not heard from the programmers. [...]
  1508.           Stated that if they could not resolve the problem then there would
  1509.           probably not be a product.
  1510.  
  1511. 03AUG92 - Final Call.  Earl claims that the programmers are unable to
  1512.           resolve the problem.  I asked if this meant that there would
  1513.           not be a product as a result and he said yes.
  1514.  
  1515.  
  1516. (g) Conclusion
  1517.  
  1518. The last report given above should put an end to the WEB story.
  1519.  
  1520. [Note from the FAQ maintainer: I intended to remove this story from
  1521. the FAQ, but the recent announcement of the MINC compressor has some
  1522. similarities with the WEB story so it is useful to keep it a little
  1523. longer.]
  1524.  
  1525. ------------------------------------------------------------------------------
  1526.  
  1527. Subject: [11] What is the V.42bis standard?
  1528.  
  1529.  
  1530. A description of the V.42bis standard is given in "The V.42bis
  1531. standard for data-compressing modems," by Clark Thomborson
  1532. <cthombor@theory.lcs.mit.edu>, IEEE Micro, Oct 1992, pp. 41-53. 
  1533.  
  1534. Short introduction, by Alejo Hausner <hausner@qucis.queensu.ca>:
  1535.  
  1536. The V.42bis Compression Standard was proposed by the International
  1537. Consultative Committee on Telephony and Telegraphy (CCITT) as an
  1538. addition to the v.42 error-correction protocol for modems. Its purpose
  1539. is to increase data throughput, and uses a variant of the
  1540. Lempel-Ziv-Welch (LZW) compression method.  It is meant to be
  1541. implemented in the modem hardware, but can also be built into the
  1542. software that interfaces to an ordinary non-compressing modem.
  1543.  
  1544. V.42bis can send data compressed or not, depending on the
  1545. data.  There are some types of data that cannot be
  1546. compressed.  For example, if a file was compressed first,
  1547. and then sent through a V.42bis modem, the modem would not
  1548. likely reduce the number of bits sent.  Indeed it is likely
  1549. that the amount of data would increase somewhat.
  1550.  
  1551. To avoid this problem, the algorithm constantly monitors the
  1552. compressibility of the data, and if it finds fewer bits
  1553. would be necessary to send it uncompressed, it switches to
  1554. transparent mode.  The sender informs the receiver of this
  1555. transition through a reserved escape code.  Henceforth the
  1556. data is passed as plain bytes.
  1557.  
  1558. The choice of escape code is clever.  Initially, it is a
  1559. zero byte.  Any occurrence of the escape code is replaced,
  1560. as is customary, by two escape codes.  In order to prevent a
  1561. string of escape codes from temporarily cutting throughput
  1562. in half, the escape code is redefined by adding 51 mod 256
  1563. each time it is used.
  1564.  
  1565. While transmitting in transparent mode, the sender maintains
  1566. the LZW trees of strings, and expects the receiver to do
  1567. likewise.  If it finds an advantage in returning to
  1568. compressed mode, it will do so, first informing the receiver
  1569. by a special control code.  Thus the method allows the
  1570. hardware to adapt to the compressibility of the data.
  1571.  
  1572.  
  1573. The CCITT standards documents used to be available by ftp on
  1574. ftp.uu.net in /doc/standards/ccitt, but this service has been
  1575. discontinued. If you ftp to digital.resource.org, in directory pub/standards
  1576. there is a file that says that making the standards available in the
  1577. first place was just an experiment.
  1578.  
  1579. The documents are now on src.doc.ic.ac.uk, but the directory name
  1580. keeps changing. Check one of:
  1581.   /computing/ccitt/ccitt-standards/ccitt/
  1582.   /computing/ccitt/standards/ccitt
  1583.   /doc/ccitt-standards/ccitt
  1584. in this order. The v42bis standard is in *standards/ccitt/1992/v/v42bis.asc.Z.
  1585.  
  1586.  
  1587. A mail server for CCITT documents is available at teledoc@itu.arcom.ch
  1588. or itudoc@itu.ch. A Gopher server is also available:
  1589.  
  1590. Name=International Telecommunication Union (ITU)
  1591. Host=info.itu.ch
  1592. Port=70
  1593.  
  1594. For more information, contact Robert Shaw <shaw@itu.arcom.ch> or
  1595. Antoinette Bautista <bautista@itu.arcom.ch>.  Warning by John Levine
  1596. <johnl@iecc.cambridge.ma.us>:
  1597.  
  1598.   This teledoc thing is much less than meets the eye.  What it
  1599.   actually has is one-page abstracts of some but not all CCITT
  1600.   recommendations, along with junk like lists of the national
  1601.   representatives to CCITT.  If you want the actual text of a
  1602.   recommendation, you have to send large amounts of money to
  1603.   Switzerland, same as ever. However, a closer reading of the Teledoc
  1604.   announcement shows that they say they're planning to make the actual
  1605.   text of some CCITT recommendations available on-line sometime in 1993.
  1606.  
  1607.  
  1608. See also the Standards FAQ posted to news.answers or get it by ftp in
  1609. rtfm.mit.edu:/pub/usenet/news.answers/standards-faq.
  1610.  
  1611. ------------------------------------------------------------------------------
  1612.  
  1613. Subject: [12] I need source for the winners of the Dr Dobbs compression contest
  1614.  
  1615.  
  1616. The source of the top 6 programs of the Feb 91 Dr Dobbs data compression
  1617. contest are available by ftp on
  1618.   oak.oakland.edu:/pub/msdos/compress/ddjcompr.zip
  1619.   garbo.uwasa.fi:/pc/source/ddjcompr.zip [128.214.87.1]
  1620.  
  1621. The sources are in MSDOS end-of-line format, one directory per
  1622. program.  Unix or VMS users, use "unzip -a ddjcompr" to get correct
  1623. end-of-lines (add -d to recreate the directory structure if you are
  1624. using an obsolete version of unzip such as 4.1). Three of the 6
  1625. programs are not portable and only run on MSDOS. compact and urban
  1626. work on Unix, sixpack only requires minor modifications.
  1627.  
  1628. ------------------------------------------------------------------------------
  1629.  
  1630. Subject: [13] I need source for arithmetic coding
  1631.  
  1632.  
  1633. (See question 70 for an introduction to arithmetic coding.)
  1634.  
  1635. The source for the arithmetic coder described in Chap.5 of Bell,
  1636. Cleary, and Witten's book "Text Compression" (see question 7 above)
  1637. (or, equivalently, in: Witten, Neal, and Cleary's article "Arithmetic
  1638. Coding for data Compression" from Communications of the Association
  1639. for Computing Machinery, 30 (6), pp.520-540, June, 1987) is available
  1640. via anonymous ftp from ftp.cpsc.ucalgary.ca (136.159.7.18) in directory
  1641. /pub/arithmetic.coding.  It only comes with a simple order-0 model but
  1642. it's set up so that adding your own more sophisticated one is
  1643. straightforward.
  1644.  
  1645. A low precision arithmetic coding implementation avoiding hardware
  1646. division is available on the same site (ftp.cpsc.ucalgary.ca)
  1647. in /pub/arithmetic.coding/low.precision.version/low.precision.version.shar.
  1648.  
  1649. Kris Popat <popat@image.mit.edu> has worked on "Scalar Quantization
  1650. with Arithmetic Coding."  It describes an arithmetic coding technique
  1651. which is quite general and computationally inexpensive.  The
  1652. documentation and example C code are available via anonymous ftp from
  1653. media-lab.media.mit.edu (18.85.0.2), in /pub/k-arith-code.
  1654.  
  1655. The program 'urban' in ddjcompr.zip (see item 12 above) is a high order
  1656. arithmetic coder working at the bit level. It is written by Urban Koistinen
  1657. <md85-epi@nada.kth.se>.
  1658.  
  1659. ------------------------------------------------------------------------------
  1660.  
  1661. Subject: [15] Where can I get image compression programs?
  1662.  
  1663.  
  1664. JPEG:
  1665.     Source code for most any machine:
  1666.     ftp.uu.net:/graphics/jpeg/jpegsrc.v4.tar.Z [137.39.1.9]
  1667.     nic.funet.fi:/pub/graphics/packages/jpeg/jpegsrc.v4.tar.Z [128.214.6.100]
  1668.     Contact: jpeg-info@uunet.uu.net (Independent JPEG Group)
  1669.  
  1670.     havefun.stanford.edu:pub/jpeg/JPEGv1.2.tar.Z (supports lossless mode)
  1671.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  1672.  
  1673.     xv, an image viewer which can read JPEG pictures, is available in
  1674.     export.lcs.mit.edu: contrib/xv-2.21.tar.Z [18.24.0.12]
  1675.  
  1676. MPEG:
  1677.     havefun.stanford.edu:/pub/mpeg/MPEGv1.2.alpha.tar.Z
  1678.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  1679.  
  1680.     toe.cs.berkeley.edu:/pub/multimedia/mpeg/mpeg_play-2.0.tar.Z
  1681.     toe.cs.berkeley.edu:/pub/multimedia/mpeg/mpeg_encode-1.0.tar.Z.
  1682.     Contact: mpeg-bugs@cs.berkeley.edu
  1683.  
  1684.     toe.cs.berkeley.edu:/pub/multimedia/mpeg/vmpeg10.zip
  1685.     decel.ecel.uwa.edu.au:/users/michael/mpegw32e.zip (for Windows and NT)
  1686.  
  1687.     nvr.com:/pub/NVR-software/Product-1.0.4.tar.Z   (192.82.231.50)
  1688.     (free demo copy of NVR's software toolkit for SPARCstations)
  1689.     Contact: Todd Brunhoff <toddb@nvr.com>
  1690.  
  1691. H.261(P*64):
  1692.     havefun.stanford.edu:pub/p64/P64v1.2.alpha.tar.Z
  1693.     Contact: Andy Hung <achung@cs.stanford.edu> (see item 20 below)
  1694.  
  1695.     ftp.inria.fr:/INRIA/ivs-2.1.tar.Z (Inria videoconference system)
  1696.  
  1697.     avahi.inria.fr:/pub/h261/h261.tar.Z (see item 20)
  1698.  
  1699. JBIG:
  1700.     nic.funet.fi:/pub/graphics/misc/test-images/jbig.tar.gz.
  1701.  
  1702. epic: (pyramid wavelet coder, see item 72)
  1703.     whitechapel.media.mit.edu:/pub/epic.tar.Z [18.85.0.125]
  1704.     Contact: Eero P. Simoncelli <eero@media.mit.edu>
  1705.     The "Lenna" test image is available as part of the EPIC package,
  1706.     where it is named "test_image".
  1707.  
  1708. hcompress: (wavelet impage compression, see item 72)
  1709.     stsci.edu:/software/hcompress/hcompress.tar.Z
  1710.  
  1711. wavethresh: (wavelet software for the language S)
  1712.     gdr.bath.ac.uk:/pub/masgpn/wavethresh2.2.Z
  1713.     Contact: gpn@maths.bath.ac.uk
  1714.  
  1715. compfits:
  1716.     uwila.cfht.hawaii.edu:/pub/compfits/compfits.tar.Z  [128.171.80.50]
  1717.     Contact: Jim Wright <jwright@cfht.hawaii.edu>
  1718.  
  1719. fitspress:
  1720.     cfata4.harvard.edu:/pub/fitspress08.tar.Z [128.103.40.79]
  1721.  
  1722. tiff:
  1723.     For source and sample images, see question 18 below.
  1724.  
  1725.  
  1726. For image compression hardware, see item 85 in part 3 of this FAQ.
  1727.  
  1728. ------------------------------------------------------------------------------
  1729.  
  1730. Subject: [16] What is the state of the art in lossless image compression?
  1731.  
  1732.  
  1733. The current state-of-the-art is the JBIG algorithm.  For an
  1734. introduction to JBIG, see question 74 in part 2.
  1735.  
  1736. JBIG works best on bi-level images (like faxes) and also works well on
  1737. Gray-coded grey scale images up to about six or so bits per pixel.  You
  1738. just apply JBIG to the bit planes individually.  For more bits/pixel,
  1739. lossless JPEG provides better performance, sometimes. (For JPEG, see
  1740. question 19 below.)
  1741.  
  1742. You can find a description of JBIG in ISO/IEC CD 11544, contained in
  1743. document ISO/IEC JTC1/SC2/N2285.  The only way to get it is to ask
  1744. your National Standards Body for a copy. In the USA, call ANSI at
  1745. (212) 642-4900.
  1746.  
  1747. ------------------------------------------------------------------------------
  1748.  
  1749. Subject: [17] What is the state of fractal compression?
  1750.  
  1751.  
  1752. from Tal Kubo <kubo@zariski.harvard.edu>:
  1753.  
  1754. According to Barnsley's book 'Fractals Everywhere', this method is
  1755. based on a measure of deviation between a given image and its
  1756. approximation by an IFS code.  The Collage Theorem states that there is
  1757. a convergent process to minimize this deviation.  Unfortunately,
  1758. according to an article Barnsley wrote for BYTE a few years ago, this
  1759. convergence was rather slow, about 100 hours on a Cray, unless assisted by
  1760. a person.
  1761.  
  1762. Barnsley et al are not divulging any technical information beyond the
  1763. meager bit in 'Fractals Everywhere'.  The book explains the idea of IFS
  1764. codes at length, but is vague about the application of the Collage theorem
  1765. to specific compression problems.
  1766.  
  1767. There is reason to believe that Barnsley's company has
  1768. *no algorithm* which takes a given reasonable image and achieves
  1769. the compression ratios initially claimed for their fractal methods.
  1770. The 1000-to-1 compression advertised was achieved only for a 'rigged'
  1771. class of images, with human assistance. The best unaided
  1772. performance I've heard of is good lossy compression of about 80-1.
  1773.  
  1774. Steve Tate <srt@duke.cs.duke.edu> confirms:
  1775.  
  1776. Compression ratios (unzoomed) seem to range from 20:1 to 60:1...  The
  1777. quality is considerably worse than wavelets or JPEG on most of the
  1778. non-contrived images I have seen.
  1779.  
  1780. But Yuval Fisher <fisher@inls1.ucsd.edu> disagrees:
  1781.  
  1782. Their performance has improved dramatically beyond what they were
  1783. talking about in BYTE a few years ago.  Human assistance to the
  1784. compression is no longer needed and the compression time is
  1785. reasonable, although the more time and compute power you throw at the
  1786. compression, the smaller the resulting file for the same level of
  1787. quality.
  1788.  
  1789. Geoffrey A Stephenson <ketlux@ketlux.demon.co.uk> adds:
  1790.  
  1791. Iterated systems are shipping a general purpose compressor at about
  1792. 300 Pounds in the UK that claims "640x480 24 bit colour compression of
  1793. about 1 min at 922k -> 10k on a 486/50 software only, decomp. to 8
  1794. bits in 3 secs, etc." At a recent multimedia conference in London they
  1795. handed out free demo disks that show the decomp. in action. The
  1796. package runs under both DOS anf WIN (DLLs provided for use in
  1797. applications). They also sell a board to speed up compression and
  1798. offer versions supporting full motion video (but not apparently at all
  1799. SVGA sizes like the static picture version). I have not yet got my
  1800. hands on a full version to test different types of pictures, but
  1801. friends have a and claim it looks good.
  1802.  
  1803.  
  1804. Thomas W. Colthurst <thomasc@athena.mit.edu> clarifies the distinction
  1805. between IFS and the Fractal Transform:
  1806.  
  1807. It is time, once and for all, to put to death the Barnsley myth that
  1808. IFSs are good for image compression.  They are not.  Various algorithms
  1809. have been proposed for this "inverse problem" ranging from the trendy
  1810. (genetic algorithms) to the deep (moment methods) to the ad hoc (the
  1811. hungry algorithm) to the absurd (the so-called "graduate student
  1812. algorithm", consisting of locking up a grad student in a tiny office
  1813. with a SGI workstation and not letting them out until they come up
  1814. with a good IFS for your image).  They are all useless for practical
  1815. image compression.
  1816.  
  1817. In fact, there are even good theoretical reasons for believing that
  1818. IFSs will never be useful for image compression.  For example, even
  1819. if you have an IFS for object A and an IFS for object B, there is no
  1820. way to combine these IFSs to get an IFS for object A union B or
  1821. object A intersect B.
  1822.  
  1823. Even Barnsley himself admits, in his latest book, that he doesn't use
  1824. IFS image compression.  Instead, he uses the so-called "fractal
  1825. transform," which is really just a variant of vector quantization
  1826. where you use the image itself, sampled at a higher scale, as the
  1827. VQ codebook.  To be fair, the fractal transform can be analyzed using
  1828. local IFSs, but local IFSs are immensely more complicated and general
  1829. than normal IFSs, to the point where one feels suspect even using the
  1830. word "IFS" to describe them.
  1831.  
  1832. It should be emphasized that the fractal transform is a real, working
  1833. method that performs about as well as other existing methods like VQ
  1834. or the discrete cosine transform. The fractal transform will probably
  1835. never beat vector quantization (VQ) as for size of the compressed
  1836. image, but does have the advantage that you don't need to carry your
  1837. codebook around.  The latest results have it slightly winning over
  1838. the discrete cosine transform; only time and more research will tell
  1839. if this advantage persists.  Just like VQ, the fractal transform
  1840. takes a while to compress, but is quick at decompression (Barnsley's
  1841. company has hardware to do this in realtime).
  1842.  
  1843. In short, IFSs are good for just about everything fractals are (and
  1844. more!), but are absolutely horrid for image compression.
  1845.  
  1846.  
  1847. Programs:
  1848.  
  1849. A fractal image compression program is available by ftp in
  1850. lyapunov.ucsd.edu:/pub/young-fractal/unifs10.zip. (Unix users, See
  1851. item 2 above for unzip on Unix.) Note the file size before you ftp it:
  1852. 1.2 MB. The package contains source for compression and decompression,
  1853. source for X-windows decompression, MSDOS executables and images.
  1854. A newer version of the program is in yuvpak20.zip.
  1855.  
  1856. A fractal image decompression program (note: decompression only) is
  1857. available in /pub/inls-ucsd/fractal-2.0.tar on on the same ftp site
  1858. (lyapunov.ucsd.edu). Note the file size before you ftp it: 1.3 MB.
  1859. This file also contains a paper by Yuval Fisher (see reference below),
  1860. and some executables and sample images. Reading this paper is required
  1861. to understand how the Young compression programs (see above) works.
  1862.  
  1863. The source code for the program published in the Oct 93 issue of
  1864. Byte is in ftp.uu.net /published/byte/93oct/fractal.exe. This is
  1865. self-extractible zip file (use "unzip fractal.exe" to extract on
  1866. non MSDOS systems). The source code is for a TARGA video board.
  1867.  
  1868.  
  1869. References:
  1870.   A. Jacquin, 'Fractal image coding based on a theory of iterated
  1871.     contractive image transformations', Visual Comm. and Image
  1872.     Processing, vol SPIE-1360, 1990. (The best paper that explains
  1873.     the concept in a simple way.)
  1874.  
  1875.   A. Jacquin, "A Fractal Theory of Iterated Markov Operators with
  1876.     Applications to Digital Image Coding", PhD Thesis, Georgia Tech, 1989.
  1877.   It can be obtained from university microfilms for $35, phone 1-800-521-0600.
  1878.  
  1879.   M. Barnsley, L. Anson, "Graphics Compression Technology, SunWorld,
  1880.     October 1991, pp. 42-52.
  1881.   M.F. Barnsley, A. Jacquin, F. Malassenet, L. Reuter & A.D. Sloan,
  1882.     'Harnessing chaos for image synthesis', Computer Graphics,
  1883.     vol 22 no 4 pp 131-140, 1988.
  1884.   M.F. Barnsley, A.E. Jacquin, 'Application of recurrent iterated
  1885.     function systems to images', Visual Comm. and Image Processing,
  1886.     vol SPIE-1001, 1988.
  1887.   A. Jacquin, "Image Coding Based on a Fractal Theory of Iterated Contractive
  1888.     Image Transformations" p.18, January 1992 (Vol 1 Issue 1) of IEEE Trans
  1889.     on Image Processing.
  1890.   A.E. Jacquin, 'A novel fractal block-coding technique for digital
  1891.     images', Proc. ICASSP 1990.
  1892.   G.E. Oien, S. Lepsoy & T.A. Ramstad, 'An inner product space
  1893.     approach to image coding by contractive transformations',
  1894.     Proc. ICASSP 1991, pp 2773-2776.
  1895.   D.S. Mazel, Fractal Modeling of Time-Series Data, PhD Thesis,
  1896.     Georgia Tech, 1991.    (One dimensional, not pictures)
  1897.   S. A. Hollatz, "Digital image compression with two-dimensional affine
  1898.     fractal interpolation functions", Department of Mathematics and
  1899.     Statistics, University of Minnesota-Duluth, Technical Report 91-2.
  1900.     (a nuts-and-bolts how-to-do-it paper on the technique)
  1901.   Stark, J., "Iterated function systems as neural networks",
  1902.     Neural Networks, Vol 4, pp 679-690, Pergamon Press, 1991.
  1903.   Monro D M and Dudbridge F, "Fractal block coding of images",
  1904.     Electronics Letters 28(11):1053-1054 (1992)
  1905.   Beaumont J M, "Image data compression using fractal techniques",
  1906.     British Telecom Technological Journal 9(4):93-108 (1991)
  1907.   Fisher Y, "Fractal image compression", Siggraph 92
  1908.   Graf S, "Barnsley's Scheme for the Fractal Encoding of Images",
  1909.     Journal Of Complexity, V8, 72-78 (1992).
  1910.   Monro D.M. 'A hybrid fractal transform', Proc ICASSP 93, pp. V: 169-72
  1911.   Monro D.M. & Dudbridge F. 'Fractal approximation of image blocks',
  1912.     Proc ICASSP 92, pp. III: 485-488
  1913.   Monro D.M., Wilson D., Nicholls J.A. 'High speed image coding with the Bath
  1914.     Fractal Transform', IEEE International Symposium on Multimedia Technologies
  1915.     Southampton, April 1993
  1916.   Jacobs, E.W., Y. Fisher and R.D. Boss.  "Image Compression:  A study
  1917.     of the Iterated Transform Method."  _Signal Processing 29_  (1992) 25-263
  1918.   Vrscay, Edward R.  "Iterated Function Systems:  Theory, Applications,
  1919.     and the Inverse Problem."  _Fractal Geometry and Analysis_,
  1920.     J. Belair and S. Dubuc (eds.)  Kluwer Academic, 1991.  405-468.
  1921.  
  1922. Books:
  1923.     The Fractal Transform,
  1924.     Michael F. Barnsley and Louisa F. Anson
  1925.     ISBN 0-86720-218-1, ca. 250 pp, $49.95
  1926.  
  1927.     Fractal Image Compression
  1928.     Michael F. Barnsley and Lyman P. Hurd
  1929.     ISBN 0-86720-457-5, ca. 250 pp., $49.95
  1930.     Copies can be ordered directly from the publisher by sending a message
  1931.     to kpeters@math.harvard.edu with name, address and a Mastercard or
  1932.     Visa card number with expiration date.
  1933.  
  1934. Barnsley's company is:
  1935.  
  1936. Iterated Systems, Inc.
  1937. 5550A Peachtree Parkway, Suite 650
  1938. Norcross, GA  30092
  1939. tel: 404-840-0310 or 1-800-4FRACTL
  1940. fax: 404-840-0806
  1941.  
  1942. ------------------------------------------------------------------------------
  1943.  
  1944. Subject: [18] I need specs and source for TIFF and CCITT group 4 Fax
  1945.  
  1946.  
  1947. Specs for Group 3 and 4 image coding (group 3 is very similar to group 4)
  1948. are in CCITT (1988) volume VII fascicle VII.3. They are recommendations
  1949. T.4 and T.6 respectively. There is also an updated spec contained in 1992
  1950. recommendations T.1 to T.6.
  1951.  
  1952. CCITT specs are available by anonymous ftp (see above answer on
  1953. V.42bis).  The T.4 and T.6 specs are on src.doc.ic.ac.uk in directory
  1954. /computing/ccitt/ccitt-standards/ccitt/1988/ascii, files 7_3_01.txt.Z and
  1955. 7_3_02.txt.Z respectively.
  1956.  
  1957. The following paper covers T.4, T.6 and JBIG:
  1958.  
  1959.   "Review of standards for electronic imaging for facsimile systems"
  1960.   in Journal of Electronic Imaging, Vol. 1, No. 1, pp. 5-21, January 1992.
  1961.  
  1962.  
  1963. Source code can be obtained as part of a TIFF toolkit - TIFF image
  1964. compression techniques for binary images include CCITT T.4 and T.6:
  1965.  
  1966.     sgi.com:/graphics/tiff/v3.2.tar.Z    [192.48.153.1]
  1967.     Contact: sam@sgi.com
  1968.  
  1969. There is also a companion compressed tar file (v3.0pics.tar.Z) that
  1970. has sample TIFF image files. A draft of TIFF 6.0 is in TIFF6.ps.Z.
  1971. Concerning JPEG compression in TIFF 6.0, Tom Lane <tgl+@cs.cmu.edu> adds:
  1972.  
  1973.   The TIFF document won't do you much good unless you also have the official
  1974.   JPEG standard. You can buy it from ANSI or your national ISO member
  1975.   organization (DIN over there, I suppose). [See also the book by Pennebaker
  1976.   and Mitchell referenced in item 75 of this FAQ.]
  1977.  
  1978.   Worse, the TIFF 6.0 spec has serious problems in its JPEG features.  It is
  1979.   probable that section 22 (JPEG) will be rewritten from scratch.  If you are
  1980.   considering implementing TIFF/JPEG, please contact me at tgl+@cs.cmu.edu for
  1981.   the latest word.
  1982.  
  1983. Software for reading and writing CCITT Group 3 and 4 images is
  1984. also available in directory merry.cs.monash.edu.au:/pub/alanf/TIFF_FAX
  1985. (130.194.67.101). Contact: Alan Finlay <alanf@bruce.cs.monash.edu.au>.
  1986.  
  1987.  
  1988. See also question 54 below.
  1989.  
  1990. ------------------------------------------------------------------------------
  1991.  
  1992. Subject: [19] What is JPEG?
  1993.  
  1994.  
  1995. JPEG (pronounced "jay-peg") is a standardized image compression mechanism.
  1996. JPEG stands for Joint Photographic Experts Group, the original name of the
  1997. committee that wrote the standard.  JPEG is designed for compressing either
  1998. full-color or gray-scale digital images of "natural", real-world scenes.
  1999. It does not work so well on non-realistic images, such as cartoons or line
  2000. drawings.
  2001.  
  2002. JPEG does not handle black-and-white (1-bit-per-pixel) images, nor does it
  2003. handle motion picture compression.  Standards for compressing those types
  2004. of images are being worked on by other committees, named JBIG and MPEG
  2005. respectively.
  2006.  
  2007. Regular JPEG is "lossy", meaning that the image you get out of decompression
  2008. isn't quite identical to what you originally put in.  The algorithm achieves
  2009. much of its compression by exploiting known limitations of the human eye,
  2010. notably the fact that small color details aren't perceived as well as small
  2011. details of light-and-dark.  Thus, JPEG is intended for compressing images that
  2012. will be looked at by humans.  If you plan to machine-analyze your images, the
  2013. small errors introduced by JPEG may be a problem for you, even if they are
  2014. invisible to the eye.  The JPEG standard includes a separate lossless mode,
  2015. but it is not widely used and does not give nearly as much compression as the
  2016. lossy mode.
  2017.  
  2018. Question 75 "Introduction to JPEG" (in part 2 of this FAQ) gives an overview
  2019. of how JPEG works and provides references for further reading.  Also see the
  2020. JPEG FAQ article, which covers JPEG software and usage hints.  The JPEG FAQ is
  2021. posted regularly in news.answers by Tom Lane <tgl+@cs.cmu.edu>.  (See question
  2022. 53 "Where are FAQ lists archived" if this posting has expired at your site.)
  2023.  
  2024. For JPEG software, see item 15 above.
  2025. For JPEG hardware, see item 85 in part 3 of this FAQ.
  2026.  
  2027. ------------------------------------------------------------------------------
  2028.  
  2029. Subject: [20] I am looking for source of an H.261 codec and MPEG
  2030.  
  2031.  
  2032. The H.261 spec is available on src.doc.ic.ac.uk in
  2033. /computing/ccitt/standards/ccitt/1992/h/h261.doc.Z (or h261.rtf.Z).
  2034.  
  2035.  
  2036. For H.261 hardware, see item 85 in part 3 of this FAQ.
  2037.  
  2038. from Thierry TURLETTI <turletti@sophia.inria.fr>:
  2039.  
  2040. We have implemented a software version of H.261 codec. 
  2041. It runs on top of UNIX and X-Windows. The coder uses the simple video capture
  2042. board "VideoPix" provided by SUN for the SparcStation. The output is directed
  2043. towards a standard TCP connection, instead of the leased lines or switched 
  2044. circuits for which regular H.261 codecs are designed. This enable us to test
  2045. video conferences over regular internet connections.
  2046. We have to polish it a bit, but the first release is now available by anonymous
  2047. ftp from avahi.inria.fr, in "/pub/h261/h261.tar.Z".
  2048.  
  2049.  
  2050. from Andy Hung <achung@cs.stanford.edu>:
  2051.  
  2052. Public domain UNIX C source code to do both image and image sequence
  2053. compression and decompression is available by anonymous ftp:
  2054.  
  2055. MPEG-I            havefun.stanford.edu:pub/mpeg/MPEGv1.2.alpha.tar.Z
  2056. CCITT H.261(P*64)    havefun.stanford.edu:pub/p64/P64v1.2.alpha.tar.Z
  2057. JPEG            havefun.stanford.edu:pub/jpeg/JPEGv1.2.beta.tar.Z
  2058.  
  2059. These codecs operate on raw raster scanned images.
  2060.  
  2061. A software program to display raw raster-scanned YUV images and image
  2062. sequences on X grayscale or color monitors is provided by a program in
  2063. the anonymous ftp directory havefun.stanford.edu pub/cv/CVv1.1.tar.Z.
  2064. If you are using the codecs above, we recommend that you ftp this file
  2065. over as well.
  2066.  
  2067. The source code has been compiled on DEC and SUN workstations.
  2068. Caution: the P64 codec has not been tested compliant (any available
  2069. p64 video streams would be much appreciated - please let us know at
  2070. achung@cs.stanford.edu).  The other codecs have been tested with
  2071. streams from other encoders.
  2072.  
  2073. We also have some IPB MPEG-I video coded streams in pub/mpeg/*.mpg;
  2074. and P64 video streams in pub/p64/*.p64 that we have generated using
  2075. our codecs.
  2076.  
  2077. For a more complete description see the file
  2078. havefun.stanford.edu:pub/README.
  2079.  
  2080. ------------------------------------------------------------------------------
  2081.  
  2082. Subject: [25] Fast DCT (Discrete Cosine Transform) algorithms
  2083.  
  2084.  
  2085. Many image compression methods, including the JPEG, MPEG, and H.261 standards,
  2086. are based on the discrete cosine transform.  A good overall introduction to
  2087. DCT is the book "Discrete Cosine Transform---Algorithms, Advantages,
  2088. Applications" by K.R. Rao and P. Yip (Academic Press, London, 1990).
  2089. This has an extensive, though already dated, bibliography.
  2090.  
  2091. Here are some newer references provided by Tom Lane <tgl+@cs.cmu.edu>.
  2092. Most of these are in IEEE journals or conference proceedings, notably
  2093. ICASSP = IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing.
  2094. ICCAS = IEEE Intl. Conf. on Circuits and Systems.
  2095. DCC = Data Compression Conference.
  2096.  
  2097. Polynomial Transform Computation of the 2-D DCT, Duhamel & Guillemot,
  2098.   ICASSP '90 p. 1515.
  2099. A Forward-Mapping Realization of the Inverse DCT, McMillan & Westover,
  2100.   DCC '92 p. 219.
  2101. A Fast Algorithm for 2-D DCT, Cho, Yun & Lee, ICASSP '91 p. 2197.
  2102. Fast Algorithm and Implementation of 2-D DCT, Cho & Lee, Tr. CAS v38 p. 297.
  2103. A DCT Chip based on a new Structured and Computationally Efficient DCT
  2104.   Algorithm, Duhamel, Guillemot & Carlach, ICCAS '90 p. 77.
  2105. Trade-offs in the Computation of Mono- and Multi-dimensional DCTs,
  2106.   Vetterli, Duhamel & Guillemot, ICASSP '89 p. 999.
  2107. Practical Fast 1-D DCT Algorithms with 11 Multiplications,
  2108.   Loeffler, Ligtenberg & Moschytz, ICASSP '89 p. 988.
  2109. New Scaled DCT Algorithms for Fused Multiply/Add Architectures,
  2110.   Linzer & Feig, ICASSP '91 p. 2201.
  2111. Fast Algorithms for the 2-D Discrete Cosine Transform, Kamangar & Rao,
  2112.   IEEE Tr. Computers, v C-31 p. 899.
  2113. Fast 2-D Discrete Cosine Transform, Vetterli, ICASSP '85 p. 1538.
  2114. A Two-Dimensional Fast Cosine Transform, Haque, Tr. ASSP v ASSP-33 p. 1532.
  2115. Real-Time Parallel and Fully Pipelined 2-D DCT Lattice Structures with
  2116.   Application to HDTV Systems, Chiu & Liu, Tr. CAS for Video Tech, v 2 p. 25.
  2117.  
  2118.  
  2119. The free JPEG code (jpegsrc.v4.tar.Z) has one of the fastest implementations
  2120. of the DCT code.  It's all in the files jfwddct.c and jrevdct.c (which do
  2121. the dct and idct, respectively). See item 15 for ftp locations.
  2122.  
  2123. ------------------------------------------------------------------------------
  2124.  
  2125. Subject: [26] Are there algorithms and standards for audio compression?
  2126.  
  2127.  
  2128. Yes. See the introduction to MPEG given in part 2 of this FAQ.
  2129.  
  2130. A lossless compressor for 8bit and 16bit audio data (.au) is available by
  2131. anonymous ftp at svr-ftp.eng.cam.ac.uk:/comp.speech/sources/shorten-1.11.tar.Z.
  2132. An MSDOS executable is in shn109.exe. Shorten works by using Huffman
  2133. coding of prediction residuals.  Compression is generally better than
  2134. that obtained by applying general purpose compression utilities to
  2135. audio files. Shorten version 1.11 also supports lossy compression.
  2136. Contact: Tony Robinson <ajr@dsl.eng.cam.ac.uk>.
  2137.  
  2138. An MPEG audio compressor is available on sunsite.unc.edu in
  2139. /pub/electronic-publications/IUMA/mpeg_players/source/mpegaudio.tar.Z.
  2140.  
  2141.  
  2142. Copied from the comp.dsp FAQ posted by guido@cwi.nl (Guido van Rossum):
  2143.  
  2144.   Strange though it seems, audio data is remarkably hard to compress
  2145.   effectively.  For 8-bit data, a Huffman encoding of the deltas between
  2146.   successive samples is relatively successful.  For 16-bit data,
  2147.   companies like Sony and Philips have spent millions to develop
  2148.   proprietary schemes.
  2149.  
  2150.   Public standards for voice compression are slowly gaining popularity,
  2151.   e.g. CCITT G.721 and G.723 (ADPCM at 32 and 24 kbits/sec).  (ADPCM ==
  2152.   Adaptive Delta Pulse Code Modulation.)  Free source code for a *fast*
  2153.   32 kbits/sec ADPCM (lossy) algorithm is available by ftp from ftp.cwi.nl
  2154.   as /pub/adpcm.shar.  (** NOTE: if you are using v1.0, you should get
  2155.   v1.1, released 17-Dec-1992, which fixes a serious bug -- the quality
  2156.   of v1.1 is claimed to be better than uLAW **)
  2157.  
  2158.   (Note that U-LAW and silence detection can also be considered
  2159.   compression schemes.)
  2160.  
  2161.  
  2162. You can get a G.721/722/723 package by email to teledoc@itu.arcom.ch, with
  2163.  
  2164. GET ITU-3022
  2165.  
  2166. as the *only* line in the body of the message.
  2167.  
  2168.  
  2169. A note on u-law from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
  2170.  
  2171.   u-law (more precisely (greek mu)-law or 5-law if you have an 8-bit
  2172.   ISO terminal) is more an encoding then a compression method,
  2173.   although a 12 to 8 bit reduction is normally part of the encoding.
  2174.   The official definition is CCITT recommendation G.711. If you want
  2175.   to know how to get CCITT documents, check the Standards FAQ
  2176.   posted to news.answers or get the file standards-faq by ftp in
  2177.   directory rtfm.mit.edu:/pub/usenet/news.answers.
  2178.  
  2179.  
  2180. See also the comp.dsp FAQ for more information on:
  2181.  
  2182. - The U.S. DoD's Federal-Standard-1016 based 4800 bps code excited linear
  2183.   prediction voice coder version 3.2a (CELP 3.2a)
  2184. - The U.S. DoD's Federal-Standard-1015/NATO-STANAG-4198 based 2400 bps
  2185.   linear prediction coder version 53 (LPC-10e v53)
  2186. - Realtime DSP code and hardware for FS-1015 and FS-1016
  2187.  
  2188. You can find the comp.dsp FAQ in comp.dsp or news.answers with subject:
  2189. "FAQ: Audio File Formats" or by ftp on rtfm.mit.edu
  2190. in /pub/usenet/news.answers/audio-fmts/part1.
  2191.  
  2192.  
  2193. CELP C code for Sun SPARCs is available for anonymous ftp at
  2194. furmint.nectar.cs.cmu.edu, in directory celp.audio.compression.
  2195. Version 3.2a is also in super.org:/pub/celp_3.2a.tar.Z.
  2196.  
  2197.  
  2198. Recommended reading:
  2199.   Digital Coding of Waveforms: Principles and Applications to Speech and
  2200.   Video.  N. S. Jayant and Peter Noll.  Prentice-Hall, 1984, ISBN
  2201.   0-13-211913-7.
  2202.  
  2203.  
  2204. from Markus Kuhn <mskuhn@immd4.informatik.uni-erlangen.de>:
  2205.  
  2206.   One highest quality sound compression format is called ASPEC and has
  2207.   been developped by a team at the Frauenhofer Institut in Erlangen (Germany)
  2208.   and others.
  2209.  
  2210.   ASPEC produces CD like quality and offers several bitrates, one is
  2211.   128 kbit/s. It is a lossy algorithm that throws away frequencys that
  2212.   aren't registered in the human cochlea in addition to sophisticated
  2213.   entropy coding. The 64 kbit/s ASPEC variant might soon bring hifi
  2214.   quality ISDN phone connections. It has been implemented on standard DSPs.
  2215.  
  2216.   The Layer 3 MPEG audio compression standard now contains what is officially
  2217.   called the best parts of the ASPEC and MUSICAM algorithms. A reference is:
  2218.  
  2219.     K.Brandenburg, G.Stoll, Y.F.Dehery, J.D.Johnston, L.v.d.Kerkhof,
  2220.     E.F.Schroeder: "The ISO/MPEG-Audio Codec: A Generic Standard for Coding
  2221.     of High Quality Digital Audio",
  2222.     92nd. AES-convention, Vienna 1992, preprint 3336
  2223.  
  2224.  
  2225. from Jutta Degener <jutta@cs.tu-berlin.de> and Carsten Bormann
  2226. <cabo@cs.tu-berlin.de>:
  2227.  
  2228.   GSM 06.10 13 kbit/s RPE/LTP speech compression available
  2229.   --------------------------------------------------------
  2230.  
  2231.   The Communications and Operating Systems Research Group (KBS) at the
  2232.   Technische Universitaet Berlin is currently working on a set of
  2233.   UNIX-based tools for computer-mediated telecooperation that will be
  2234.   made freely available.
  2235.  
  2236.   As part of this effort we are publishing an implementation of the
  2237.   European GSM 06.10 provisional standard for full-rate speech
  2238.   transcoding, prI-ETS 300 036, which uses RPE/LTP (residual pulse
  2239.   excitation/long term prediction) coding at 13 kbit/s.
  2240.  
  2241.   GSM 06.10 compresses frames of 160 13-bit samples (8 kHz sampling
  2242.   rate, i.e. a frame rate of 50 Hz) into 260 bits; for compatibility
  2243.   with typical UNIX applications, our implementation turns frames of 160
  2244.   16-bit linear samples into 33-byte frames (1650 Bytes/s).
  2245.   The quality of the algorithm is good enough for reliable speaker
  2246.   recognition; even music often survives transcoding in recognizable 
  2247.   form (given the bandwidth limitations of 8 kHz sampling rate).
  2248.  
  2249.   Version 1.0 of the implementation is available per anonymous ftp from
  2250.   tub.cs.tu-berlin.de as /pub/tubmik/gsm-1.0.tar.Z.  Questions and bug
  2251.   reports should be directed to toast@tub.cs.tu-berlin.de.  
  2252.   Note that the distribution is not available via E-mail (please use one
  2253.   of the ftp-via-E-mail servers).
  2254.  
  2255.  
  2256. from Bob Kimball <rkimball@qualcomm.com>:
  2257.  
  2258.   I work for Qualcomm Inc. and we are designing a digital cellular telephone
  2259.   system.  Our phone uses our variable rate vocoder (QCELP) which is designed
  2260.   for speach and compresses 64Kb/s speach to 8Kb/s through 1Kb/s with 8Kb/s
  2261.   being full rate and 1Kb/s for 1/8 rate speach.  It works great for speach.
  2262.  
  2263.   The QCELP process is documented in our Common Air Interface (CAI) which is
  2264.   available for anonymous ftp from lorien.qualcomm.com in /pub/cdma
  2265.   each chapter is a postscript file.  The vocoder is described in appendix A.
  2266.   The whole document is quite large.  This is the document which is currently
  2267.   going through the TIA standard committee so it is not a final version.  The
  2268.   appendix on the vocoder should be almost identical to the final version...
  2269.   whenever that comes out.
  2270.  
  2271.  
  2272. from Nicola Ferioli <ser1509@cdc835.cdc.polimi.it>:
  2273.  
  2274.   oak.oakland.edu:/pub/msdos/sound/vocpak20.zip
  2275.     Lossless 8-bit sound file compressor
  2276.  
  2277.   VOCPACK is a compressor/decompressor for 8-bit digital sound using a
  2278.   lossless algorithm; it is useful to save disk space without degrading
  2279.   sound quality.  It can compress signed and unsigned data, sampled at any
  2280.   rate, mono or stereo.  Since the method used is not lossy, it isn't
  2281.   necessary to strip file headers before compressing.
  2282.  
  2283.   VOCPACK was developed for use with .VOC (SoundBlaster) and .WAV (Windows)
  2284.   files, but any 8-bit sound can be compressed since the program takes no
  2285.   assumptions about the file structure.
  2286.  
  2287.   The typical compression ratio obtained goes from 0,8 for files sampled at
  2288.   11 KHz to 0,4 for 44 Khz files.  The best results are obtained with 44 KHz
  2289.   sounds (mono or stereo): general-purpose archivers create files that can be
  2290.   twice longer than the output of VOCPACK.  You can obtain smaller values
  2291.   using lossy compressors but if your goal is to keep the sound quality
  2292.   unaltered you should use a lossless program like VOCPACK.
  2293.  
  2294. ------------------------------------------------------------------------------
  2295.  
  2296. Subject: [30] My archive is corrupted!
  2297.  
  2298.  
  2299. The two most common reasons for this are
  2300.  
  2301. (1) failing to use the magic word "tenex" (when connected to SIMTEL20 and
  2302.     other TOPS20 systems) or "binary" (when connected to UNIX systems) when
  2303.     transferring the file from an ftp site to your host machine.  The
  2304.     reasons for this are technical and boring.  A synonym for "tenex" is
  2305.     "type L 8", in case your ftp doesn't know what "tenex" means.
  2306.  
  2307. (2) failing to use an eight-bit binary transfer protocol when transferring
  2308.     the file from the host to your PC.  Make sure to set the transfer type
  2309.     to "binary" on both your host machine and your PC.
  2310.  
  2311. ------------------------------------------------------------------------------
  2312.  
  2313. Subject: [31] pkunzip reports a CRC error!
  2314.  
  2315.  
  2316. The portable zip 1.1 contains many workarounds for undocumented restrictions
  2317. in pkunzip. Compatibility is ensured for pkunzip 1.10 only. All previous
  2318. versions (pkunzip 1.0x) have too many bugs and cannot be supported. This
  2319. includes Borland unzip.
  2320.  
  2321. So if your pkunzip reports a CRC error, check that you are not using
  2322. an obsolete version. Get either pkzip 2.04g or unzip 5.0p1 (see question
  2323. 2 above for ftp sites). To generate zip files compatible with pkunzip 1.10,
  2324. use zip 1.1 (see item 2 above for ftp site).
  2325.  
  2326. ------------------------------------------------------------------------------
  2327.  
  2328. Subject: [32] VMS zip is not compatible with pkzip!
  2329.  
  2330.  
  2331. The problem is most likely in the file transfer program.
  2332.  
  2333. Many use kermit to transfer zipped files between PC and VMS VAX.  The
  2334. following VMS kermit settings make VMS-ZIP compatible with PKZIP:
  2335.  
  2336.                                              VMS kermit        PC kermit
  2337.                                            ---------------   --------------
  2338.  
  2339. Uploading PKZIPped file to be UNZIPped:    set fi ty fixed    set fi ty bi
  2340. Downloading ZIPped file to be PKUNZIPped:  set fi ty block    set fi ty bi
  2341.  
  2342. If you are not using kermit, transfer a file created by pkzip on MSDOS
  2343. to VMS, transfer it back to your PC and check that pkunzip can extract it.
  2344.  
  2345. ------------------------------------------------------------------------------
  2346.  
  2347. Subject: [33] I have a problem with Stacker!
  2348.  
  2349.  
  2350. The newsgroup comp.compression is *not* the appropriate place to
  2351. discuss about one specific program on one specific operating system.
  2352. Since you have bought a legal copy of Stacker, you have the
  2353. documentation of your product; please read it. If you can't find the
  2354. answer in the documentation, please report the problem to the Stac
  2355. customer support.  If you really feel that the net has to know about
  2356. your problem, please post in one of the MSDOS newsgroups, such as
  2357. comp.os.msdos.apps or comp.binaries.ibm.pc.d.
  2358.  
  2359. ------------------------------------------------------------------------------
  2360.  
  2361. Subject: [50] What is this 'tar' compression program?
  2362.  
  2363.  
  2364. tar is not a compression program. It just combines several files
  2365. into one, without compressing them. tar file are often compressed with
  2366. 'compress', resulting in a .tar.Z file. See question 2, file type .tar.Z.
  2367. GNU tar has the capability to (de)compress files as well.
  2368.  
  2369. When you have to archive a lot of very small files, it is often
  2370. preferable to create a single .tar file and compress it, than to
  2371. compress the individual files separately. The compression program can
  2372. thus take advantage of redundancy between separate files.  The
  2373. disadvantage is that you must uncompress the whole .tar file to
  2374. extract any member. You can also improve compression by grouping
  2375. files by type, as in:
  2376.  
  2377.   tar cvf - `ls | sort -t. +1` | gzip > file.tar.gz
  2378.  
  2379. ------------------------------------------------------------------------------
  2380.  
  2381. Subject: [51] I need a CRC algorithm
  2382.  
  2383.  
  2384. As its name implies (Cyclic Redundancy Check) a crc adds redundancy
  2385. whereas the topic of this group is to remove it. But since this
  2386. question comes up often, here is some code (by Rob Warnock <rpw3@sgi.com>).
  2387.  
  2388. The following C code does CRC-32 in BigEndian/BigEndian byte/bit order.
  2389. That is, the data is sent most significant byte first, and each of the bits
  2390. within a byte is sent most significant bit first, as in FDDI. You will need
  2391. to twiddle with it to do Ethernet CRC, i.e., BigEndian/LittleEndian byte/bit
  2392. order. [Left as an exercise for the reader.]
  2393.  
  2394. The CRCs this code generates agree with the vendor-supplied Verilog models
  2395. of several of the popular FDDI "MAC" chips.
  2396.  
  2397. u_long crc32_table[256];
  2398. /* Initialized first time "crc32()" is called. If you prefer, you can
  2399.  * statically initialize it at compile time. [Another exercise.]
  2400.  */
  2401.  
  2402. u_long crc32(u_char *buf, int len)
  2403. {
  2404.         u_char *p;
  2405.         u_long  crc;
  2406.  
  2407.         if (!crc32_table[1])    /* if not already done, */
  2408.                 init_crc32();   /* build table */
  2409.         crc = 0xffffffff;       /* preload shift register, per CRC-32 spec */
  2410.         for (p = buf; len > 0; ++p, --len)
  2411.                 crc = (crc << 8) ^ crc32_table[(crc >> 24) ^ *p];
  2412.         return ~crc;            /* transmit complement, per CRC-32 spec */
  2413. }
  2414.  
  2415. /*
  2416.  * Build auxiliary table for parallel byte-at-a-time CRC-32.
  2417.  */
  2418. #define CRC32_POLY 0x04c11db7     /* AUTODIN II, Ethernet, & FDDI */
  2419.  
  2420. init_crc32()
  2421. {
  2422.         int i, j;
  2423.         u_long c;
  2424.  
  2425.         for (i = 0; i < 256; ++i) {
  2426.                 for (c = i << 24, j = 8; j > 0; --j)
  2427.                         c = c & 0x80000000 ? (c << 1) ^ CRC32_POLY : (c << 1);
  2428.                 crc32_table[i] = c;
  2429.         }
  2430. }
  2431.  
  2432. See also ftp.uni-erlangen.de:/pub/doc/ISO/english/async-HDLC, and the
  2433. source of all archivers, such as the file makecrc.c in the sources of
  2434. zip 2.0 (see item 2).
  2435.  
  2436. ------------------------------------------------------------------------------
  2437.  
  2438. Subject: [52] What about those people who continue to ask frequently asked
  2439.               questions in spite of the frequently asked questions document?
  2440.  
  2441.  
  2442. Just send them a polite mail message, referring them to this document.
  2443. There is no need to flame them on comp.compression.  That would just
  2444. add more noise to this group.  Posted answers that are in the FAQ are
  2445. just as annoying as posted questions that are in the FAQ.
  2446.  
  2447. ------------------------------------------------------------------------------
  2448.  
  2449. Subject: [53] Where are FAQ lists archived?
  2450.  
  2451.  
  2452. Many are crossposted to news.answers.  That newsgroup should have a
  2453. long expiry time at your site; if not, talk to your sysadmin.
  2454.  
  2455. FAQ lists are available by anonymous FTP from rtfm.mit.edu.
  2456. The comp.compression FAQ that you are reading is in directory
  2457.    /pub/usenet/news.answers/compression-faq
  2458.  
  2459. If you don't have FTP access, you can access the archives by mail
  2460. server.  Send an email message to mail-server@rtfm.mit.edu
  2461. containing the commands
  2462.     send usenet/news.answers/compression-faq/part1
  2463.     send usenet/news.answers/compression-faq/part2
  2464.     send usenet/news.answers/compression-faq/part3
  2465. For instructions, send an email message to the same address with the
  2466. words "help" and "index" (no quotes) on separate lines. If you don't
  2467. get a reply, check your return address, or add a line such as
  2468.     path myname@foo.edu
  2469.  
  2470. ------------------------------------------------------------------------------
  2471.  
  2472. Subject: [54] I need specs for graphics formats
  2473.  
  2474.  
  2475. Have a look in directory /pub/graphics.formats on zamenhof.cs.rice.edu.
  2476. It contains descriptions of gif, tiff, fits, etc...
  2477.  
  2478. See also the FAQ list for comp.graphics. See item 53 for an ftp site.
  2479.  
  2480. ------------------------------------------------------------------------------
  2481.  
  2482. Subject: [55] Where can I find Lenna and other images?
  2483.  
  2484.  
  2485. A bunch of standard images (lenna, baboon, cameraman, crowd, moon
  2486. etc..) are on ftp site eedsp.gatech.edu (130.207.226.2) in directory
  2487. /database/images. The images are in 256-level grayshades (256x256
  2488. pixels, 256 "colors").
  2489.  
  2490. [Note: the site ipl.rpi.edu mentioned below keeps changing. Images
  2491. stay there for a while then disappear. They are again available at
  2492. the time of writing (27 Dec 93).]
  2493.  
  2494. The site ipl.rpi.edu (128.113.14.50) has standard images in two
  2495. directories:
  2496.    ipl.rpi.edu:/pub/image/still/usc 
  2497.    ipl.rpi.edu:/pub/image/still/canon
  2498.  
  2499. (The directory /pub/image/sequence was taken offline because of
  2500. possible copyright problems, but has come back again. In particular,
  2501. Miss America is in subdirectories of /pub/image/sequence/missa.)
  2502.  
  2503. In each of those directories are the following directories:
  2504.    bgr     - 24 bit blue, green, red
  2505.    color   - 24 bit red, green, blue
  2506.    gray    - 8 bit grayscale uniform weighted
  2507.    gray601 - 8 bit grayscale CCIR-601 weighted
  2508.  
  2509. And in these directories are the actual images.  
  2510.  
  2511. For example, the popular lena image is in
  2512.    ipl.rpi.edu:/pub/image/still/usc/color/lena  # 24 bit RGB
  2513.    ipl.rpi.edu:/pub/image/still/usc/bgr/lena    # 24 bit BGR
  2514.    ipl.rpi.edu:/pub/image/still/usc/gray/lena   # 8 bit gray
  2515.  
  2516. All of the images are in Sun rasterfile format.  You can use the pbm
  2517. utilities to convert them to whatever format is most convenient.
  2518. [pbm is available in ftp.ee.lbl.gov:/pbmplus*.tar.Z].
  2519. Questions about the ipl archive should be sent to help@ipl.rpi.edu.
  2520.  
  2521.  
  2522. There are few gray-scale still images and some raw data of test results
  2523. available in directory nic.funet.fi:/pub/graphics/misc/test-images.
  2524.  
  2525. Medical images can be found in decaf.stanford.edu:/pub/images/medical/mri.
  2526.  
  2527. Rodney Peck <rodney@balltown.cma.com> is interested in some method
  2528. of establishing a canonical ftp database of images but does not have
  2529. the resources to provide an ftp site for that database. Send suggestions to
  2530. rodney@balltown.cma.com.
  2531.  
  2532.  
  2533. Beware: the same image often comes in many different forms, at
  2534. different resolutions, etc... The original lenna image is 512 wide,
  2535. 512 high, 8 bits per pel, red, green and blue fields.  Gray-scale
  2536. versions of Lenna have been obtained in two different ways from the
  2537. original:
  2538.  (1) Using the green field as a gray-scale image, and
  2539.  (2) Doing an RGB->YUV transformation and saving the Y component.
  2540. Method (1) makes it easier to compare different people's results since
  2541. everyone's version should be the same using that method.  Method (2)
  2542. produces a more correct image.
  2543.  
  2544. For the curious: 'lena' or 'lenna' is a digitized Playboy centerfold,
  2545. from November 1972. (Lenna is the spelling in Playboy, Lena is the
  2546. Swedish spelling of the name.) Lena Soderberg (ne Sjooblom) was last
  2547. reported living in her native Sweden, happily married with three kids
  2548. and a job with the state liquor monopoly.  In 1988, she was
  2549. interviewed by some Swedish computer related publication, and she was
  2550. pleasantly amused by what had happened to her picture.  That was the
  2551. first she knew of the use of that picture in the computer business.
  2552.  
  2553. The editorial in the January 1992 issue of Optical Engineering (v. 31
  2554. no. 1) details how Playboy has finally caught on to the fact that
  2555. their copyright on Lenna Sjooblom's photo is being widely infringed.
  2556. It sounds as if you will have to get permission from Playboy to
  2557. publish it in the future.
  2558.  
  2559.  
  2560. Note on the CCITT test images, by Robert Estes <estes@eecs.ucdavis.edu>:
  2561.  
  2562. The ccitt files are in ipl.rpi.edu:/image-archive/bitmap/ccitt
  2563. (128.113.14.50). They are named ccitt-n.ras.Z where n goes from 1 to 8.
  2564. Each file has an accompanying doc file called ccitt-n.ras.doc which
  2565. describes the image file. Here's the doc file for ccitt-1.ras:
  2566.  
  2567. Name ccitt-1.ras
  2568. Size 1728 x 2376 x 1
  2569. Type 1 bit standard format sun rasterfile 
  2570. Keywords binary standard image 1 bit fax
  2571. Description
  2572. One of eight images from the standard binary CCITT test image set.
  2573.  
  2574. This set is commonly used to compare binary image compression
  2575. techniques. The images are are 1728x2376 pixels.
  2576.  
  2577. ------------------------------------------------------------------------------
  2578.  
  2579. Subject: [56] I am looking for a message digest algorithm
  2580.  
  2581.  
  2582. Look on the ftp site rsa.com, in directory /pub. MD4 and MD5 are there.
  2583. This question would be more appropriate on sci.crypt.
  2584.  
  2585.  
  2586.  
  2587.           End of part 1 of the comp.compression faq.
  2588.  
  2589.  
  2590. Article: 9669 of comp.compression
  2591. Path: chorus!chorus.fr
  2592. From: jloup@chorus.fr (Jean-loup Gailly)
  2593. Newsgroups: comp.compression,comp.compression.research,news.answers,comp.answers
  2594. Subject: comp.compression Frequently Asked Questions (part 2/3)
  2595. Summary: *** READ THIS BEFORE POSTING ***
  2596. Keywords: data compression, FAQ
  2597. Message-ID: <compr2_21feb94@chorus.fr>
  2598. Date: 21 Feb 94 16:54:36 GMT
  2599. Expires: 30 Mar 94 16:17:20 GMT
  2600. References: <compr1_21feb94@chorus.fr>
  2601. Sender: news@chorus.chorus.fr
  2602. Reply-To: jloup@chorus.fr
  2603. Followup-To: comp.compression
  2604. Lines: 1159
  2605. Approved: news-answers-request@MIT.Edu
  2606. Supersedes: <compr2_17jan94@chorus.fr>
  2607. Xref: chorus comp.compression:9669 comp.compression.research:1190 news.answers:17959 comp.answers:3824
  2608.  
  2609. Archive-name: compression-faq/part2
  2610. Last-modified: Jan 17th, 1994
  2611.  
  2612. This file is part 2 of a set of Frequently Asked Questions for the
  2613. groups comp.compression and comp.compression.research.
  2614. If you did not get part 1 or 3, you can get them by ftp
  2615. on rtfm.mit.edu in directory
  2616.    /pub/usenet/news.answers/compression-faq
  2617.  
  2618. If you don't want to see this FAQ regularly, please add the subject
  2619. line to your kill file. If you have corrections or suggestions for
  2620. this FAQ, send them to Jean-loup Gailly <jloup@chorus.fr>.  Thank you.
  2621.  
  2622. Contents
  2623. ========
  2624.  
  2625. Part 2: (Long) introductions to data compression techniques
  2626.  
  2627. [70] Introduction to data compression (long)
  2628.        Huffman and Related Compression Techniques
  2629.        Arithmetic Coding
  2630.        Substitutional Compressors
  2631.           The LZ78 family of compressors
  2632.           The LZ77 family of compressors
  2633.  
  2634. [71] Introduction to MPEG (long)
  2635.        What is MPEG?
  2636.        Does it have anything to do with JPEG?
  2637.        Then what's JBIG and MHEG?
  2638.        What has MPEG accomplished?
  2639.        So how does MPEG I work?
  2640.        What about the audio compression?
  2641.        So how much does it compress?
  2642.        What's phase II?
  2643.        When will all this be finished?
  2644.        How do I join MPEG?
  2645.        How do I get the documents, like the MPEG I draft?
  2646.  
  2647. [72] What is wavelet theory?
  2648. [73] What is the theoretical compression limit?
  2649. [74] Introduction to JBIG
  2650. [75] Introduction to JPEG
  2651.  
  2652. Part 3: (Long) list of image compression hardware
  2653.  
  2654. [85] Image compression hardware
  2655. [99] Acknowledgments
  2656.  
  2657.  
  2658. Search for "Subject: [#]" to get to question number # quickly. Some news
  2659. readers can also take advantage of the message digest format used here.
  2660.  
  2661. ------------------------------------------------------------------------------
  2662.  
  2663. Subject: [70] Introduction to data compression (long)
  2664.  
  2665.  
  2666. Written by Peter Gutmann <pgut1@cs.aukuni.ac.nz>.
  2667.  
  2668.  Huffman and Related Compression Techniques
  2669.  ------------------------------------------
  2670.  
  2671.   *Huffman compression* is a statistical data compression technique which 
  2672. gives a reduction in the average code length used to represent the symbols of 
  2673. a alphabet.  The Huffman code is an example of a code which is optimal in the 
  2674. case where all symbols probabilities are integral powers of 1/2.  A Huffman 
  2675. code can be built in the following manner:
  2676.  
  2677.   (1) Rank all symbols in order of probability of occurrence.
  2678.     
  2679.   (2) Successively combine the two symbols of the lowest probability to form
  2680.       a new composite symbol; eventually we will build a binary tree where
  2681.       each node is the probability of all nodes beneath it.
  2682.  
  2683.   (3) Trace a path to each leaf, noticing the direction at each node.
  2684.  
  2685.   For a given frequency distribution, there are many possible Huffman codes,
  2686. but the total compressed length will be the same. It is possible to
  2687. define a 'canonical' Huffman tree, that is, pick one of these alternative
  2688. trees. Such a canonical tree can then be represented very compactly, by
  2689. transmitting only the bit length of each code. This technique is used
  2690. in most archivers (pkzip, lha, zoo, arj, ...).
  2691.  
  2692.  
  2693.   A technique related to Huffman coding is *Shannon-Fano coding*, which
  2694. works as follows:
  2695.  
  2696.   (1) Divide the set of symbols into two equal or almost equal subsets
  2697.       based on the probability of occurrence of characters in each
  2698.       subset.  The first subset is assigned a binary zero, the second
  2699.       a binary one.
  2700.  
  2701.   (2) Repeat step (1) until all subsets have a single element.
  2702.  
  2703. The algorithm used to create the Huffman codes is bottom-up, and the
  2704. one for the Shannon-Fano codes is top-down. Huffman encoding always
  2705. generates optimal codes, Shannon-Fano sometimes uses a few more bits.
  2706.  
  2707.  
  2708.  Arithmetic Coding
  2709.  -----------------
  2710.  
  2711.   It would appear that Huffman or Shannon-Fano coding is the perfect
  2712. means of compressing data.  However, this is *not* the case.  As
  2713. mentioned above, these coding methods are optimal when and only when
  2714. the symbol probabilities are integral powers of 1/2, which is usually
  2715. not the case.
  2716.  
  2717.   The technique of *arithmetic coding* does not have this restriction:
  2718. It achieves the same effect as treating the message as one single unit
  2719. (a technique which would, for Huffman coding, require enumeration of
  2720. every single possible message), and thus attains the theoretical
  2721. entropy bound to compression efficiency for any source.
  2722.  
  2723.   Arithmetic coding works by representing a number by an interval of real 
  2724. numbers between 0 and 1.  As the message becomes longer, the interval needed 
  2725. to represent it becomes smaller and smaller, and the number of bits needed to 
  2726. specify that interval increases.  Successive symbols in the message reduce 
  2727. this interval in accordance with the probability of that symbol. The more
  2728. likely symbols reduce the range by less, and thus add fewer bits to the   
  2729. message.
  2730.  
  2731.      1                                             Codewords
  2732.     +-----------+-----------+-----------+           /-----\
  2733.     |           |8/9 YY     |  Detail   |<- 31/32    .11111
  2734.     |           +-----------+-----------+<- 15/16    .1111
  2735.     |    Y      |           | too small |<- 14/16    .1110
  2736.     |2/3        |    YX     | for text  |<- 6/8      .110
  2737.     +-----------+-----------+-----------+
  2738.     |           |           |16/27 XYY  |<- 10/16    .1010
  2739.     |           |           +-----------+
  2740.     |           |    XY     |           |
  2741.     |           |           |   XYX     |<- 4/8      .100
  2742.     |           |4/9        |           |
  2743.     |           +-----------+-----------+
  2744.     |           |           |           |
  2745.     |    X      |           |   XXY     |<- 3/8      .011
  2746.     |           |           |8/27       |
  2747.     |           |           +-----------+
  2748.     |           |    XX     |           |
  2749.     |           |           |           |<- 1/4      .01
  2750.     |           |           |   XXX     |
  2751.     |           |           |           |
  2752.     |0          |           |           |
  2753.     +-----------+-----------+-----------+
  2754.  
  2755.   As an example of arithmetic coding, lets consider the example of two
  2756. symbols X and Y, of probabilities 0.66 and 0.33. To encode this message, we
  2757. examine the first symbol: If it is a X, we choose the lower partition; if
  2758. it is a Y, we choose the upper partition.  Continuing in this manner for
  2759. three symbols, we get the codewords shown to the right of the diagram above
  2760. - they can be found by simply taking an appropriate location in the
  2761. interval for that particular set of symbols and turning it into a binary
  2762. fraction. In practice, it is also necessary to add a special end-of-data
  2763. symbol, which is not represented in this simpe example.
  2764.         
  2765.   In this case the arithmetic code is not completely efficient, which is due 
  2766. to the shortness of the message - with longer messages the coding efficiency 
  2767. does indeed approach 100%.
  2768.  
  2769.   Now that we have an efficient encoding technique, what can we do with it? 
  2770. What we need is a technique for building a model of the data which we can 
  2771. then use with the encoder.  The simplest model is a fixed one, for example a 
  2772. table of standard letter frequencies for English text which we can then use 
  2773. to get letter probabilities.  An improvement on this technique is to use an 
  2774. *adaptive model*, in other words a model which adjusts itself to the data 
  2775. which is being compressed as the data is compressed.  We can convert the 
  2776. fixed model into an adaptive one by adjusting the symbol frequencies after 
  2777. each new symbol is encoded, allowing the model to track the data being 
  2778. transmitted.  However, we can do much better than that.
  2779.  
  2780. Using the symbol probabilities by themselves is not a particularly good
  2781. estimate of the true entropy of the data: We can take into account
  2782. intersymbol probabilities as well.  The best compressors available today
  2783. take this approach: DMC (Dynamic Markov Coding) starts with a zero-order
  2784. Markov model and gradually extends this initial model as compression
  2785. progresses; PPM (Prediction by Partial Matching) looks for a match of the
  2786. text to be compressed in an order-n context.  If no match is found, it
  2787. drops to an order n-1 context, until it reaches order 0.  Both these
  2788. techniques thus obtain a much better model of the data to be compressed,
  2789. which, combined with the use of arithmetic coding, results in superior
  2790. compression performance.
  2791.  
  2792.   So if arithmetic coding-based compressors are so powerful, why are they not 
  2793. used universally?  Apart from the fact that they are relatively new and 
  2794. haven't come into general use too much yet, there is also one major concern:  
  2795. The fact that they consume rather large amounts of computing resources, both 
  2796. in terms of CPU power and memory.  The building of sophisticated models for 
  2797. the compression can chew through a fair amount of memory (especially in the 
  2798. case of DMC, where the model can grow without bounds); and the arithmetic 
  2799. coding itself involves a fair amount of number crunching.
  2800. There is however an alternative approach, a class of compressors generally 
  2801. referred to as *substitutional* or *dictionary-based compressors*.
  2802.  
  2803.  Substitutional Compressors
  2804.  --------------------------
  2805.  
  2806.   The basic idea behind a substitutional compressor is to replace an 
  2807. occurrence of a particular phrase or group of bytes in a piece of data with a 
  2808. reference to a previous occurrence of that phrase.  There are two main 
  2809. classes of schemes, named after Jakob Ziv and Abraham Lempel, who first 
  2810. proposed them in 1977 and 1978.
  2811.  
  2812. <The LZ78 family of compressors>
  2813.  
  2814.   LZ78-based schemes work by entering phrases into a *dictionary* and then, 
  2815. when a repeat occurrence of that particular phrase is found, outputting the 
  2816. dictionary index instead of the phrase.  There exist several compression 
  2817. algorithms based on this principle, differing mainly in the manner in which 
  2818. they manage the dictionary.  The most well-known scheme (in fact the most 
  2819. well-known of all the Lempel-Ziv compressors, the one which is generally (and 
  2820. mistakenly) referred to as "Lempel-Ziv Compression"), is Terry Welch's LZW 
  2821. scheme, which he designed in 1984 for implementation in hardware for high- 
  2822. performance disk controllers.
  2823.  
  2824. Input string: /WED/WE/WEE/WEB
  2825.  
  2826. Character input:    Code output:    New code value and associated string:
  2827.     /W                  /                   256 = /W
  2828.     E                   W                   257 = WE
  2829.     D                   E                   258 = ED
  2830.     /                   D                   259 = D/
  2831.     WE                  256                 260 = /WE
  2832.     /                   E                   261 = E/
  2833.     WEE                 260                 262 = /WEE
  2834.     /W                  261                 263 = E/W
  2835.     EB                  257                 264 = WEB
  2836.     <END>               B
  2837.     
  2838.   LZW starts with a 4K dictionary, of which entries 0-255 refer to individual 
  2839. bytes, and entries 256-4095 refer to substrings.  Each time a new code is 
  2840. generated it means a new string has been parsed.  New strings are generated 
  2841. by appending the current character K to the end of an existing string w.  The 
  2842. algorithm for LZW compression is as follows:
  2843.  
  2844.   set w = NIL
  2845.   loop
  2846.       read a character K
  2847.       if wK exists is in the dictionary
  2848.           w = wK
  2849.       else
  2850.           output the code for w
  2851.           add wK to the string table
  2852.           w = K
  2853.   endloop
  2854.  
  2855.   A sample run of LZW over a (highly redundant) input string can be seen in 
  2856. the diagram above.  The strings are built up character-by-character starting 
  2857. with a code value of 256.  LZW decompression takes the stream of codes and 
  2858. uses it to exactly recreate the original input data.  Just like the 
  2859. compression algorithm, the decompressor adds a new string to the dictionary 
  2860. each time it reads in a new code.  All it needs to do in addition is to 
  2861. translate each incoming code into a string and send it to the output.  A 
  2862. sample run of the LZW decompressor is shown in below.
  2863.  
  2864. Input code: /WED<256>E<260><261><257>B
  2865.  
  2866. Input code:        Output string:     New code value and associated string:
  2867.     /                  /            
  2868.     W                  W                      256 = /W
  2869.     E                  E                      257 = WE
  2870.     D                  D                      258 = ED
  2871.     256                /W                     259 = D/
  2872.     E                  E                      260 = /WE
  2873.     260                /WE                    261 = E/
  2874.     261                E/                     262 = /WEE
  2875.     257                WE                     263 = E/W
  2876.     B                  B                      264 = WEB
  2877.            
  2878.   The most remarkable feature of this type of compression is that the entire 
  2879. dictionary has been transmitted to the decoder without actually explicitly 
  2880. transmitting the dictionary.  At the end of the run, the decoder will have a 
  2881. dictionary identical to the one the encoder has, built up entirely as part of 
  2882. the decoding process.
  2883.     LZW is more commonly encountered today in a variant known as LZC, after 
  2884. its use in the UNIX "compress" program.  In this variant, pointers do not 
  2885. have a fixed length.  Rather, they start with a length of 9 bits, and then 
  2886. slowly grow to their maximum possible length once all the pointers of a 
  2887. particular size have been used up.  Furthermore, the dictionary is not frozen 
  2888. once it is full as for LZW - the program continually monitors compression 
  2889. performance, and once this starts decreasing the entire dictionary is 
  2890. discarded and rebuilt from scratch.  More recent schemes use some sort of 
  2891. least-recently-used algorithm to discard little-used phrases once the 
  2892. dictionary becomes full rather than throwing away the entire dictionary.  
  2893.  
  2894. Finally, not all schemes build up the dictionary by adding a single new 
  2895. character to the end of the current phrase. An alternative technique is to 
  2896. concatenate the previous two phrases (LZMW), which results in a faster 
  2897. buildup of longer phrases than the character-by-character buildup of the 
  2898. other methods.  The disadvantage of this method is that a more sophisticated 
  2899. data structure is needed to handle the dictionary.
  2900.  
  2901. [A good introduction to LZW, MW, AP and Y coding is given in the yabba
  2902. package. For ftp information, see question 2 in part one, file type .Y]
  2903.  
  2904.  
  2905. <The LZ77 family of compressors>
  2906.  
  2907.   LZ77-based schemes keep track of the last n bytes of data seen, and when a 
  2908. phrase is encountered that has already been seen, they output a pair of 
  2909. values corresponding to the position of the phrase in the previously-seen 
  2910. buffer of data, and the length of the phrase.  In effect the compressor moves 
  2911. a fixed-size *window* over the data (generally referred to as a *sliding 
  2912. window*), with the position part of the (position, length) pair referring to 
  2913. the position of the phrase within the window.  The most commonly used 
  2914. algorithms are derived from the LZSS scheme described by James Storer and 
  2915. Thomas Szymanski in 1982.  In this the compressor maintains a window of size 
  2916. N bytes and a *lookahead buffer* the contents of which it tries to find a 
  2917. match for in the window:
  2918.  
  2919.   while( lookAheadBuffer not empty )
  2920.       {
  2921.       get a pointer ( position, match ) to the longest match in the window
  2922.           for the lookahead buffer;
  2923.  
  2924.       if( length > MINIMUM_MATCH_LENGTH )
  2925.           {
  2926.           output a ( position, length ) pair;
  2927.           shift the window length characters along;
  2928.           }
  2929.       else
  2930.           {
  2931.           output the first character in the lookahead buffer;
  2932.           shift the window 1 character along;
  2933.           }
  2934.       }
  2935.         
  2936.   Decompression is simple and fast:  Whenever a ( position, length ) pair is 
  2937. encountered, go to that ( position ) in the window and copy ( length ) bytes 
  2938. to the output.
  2939.  
  2940.   Sliding-window-based schemes can be simplified by numbering the input text
  2941. characters mod N, in effect creating a circular buffer.  The sliding window
  2942. approach automatically creates the LRU effect which must be done explicitly in
  2943. LZ78 schemes.  Variants of this method apply additional compression to the
  2944. output of the LZSS compressor, which include a simple variable-length code
  2945. (LZB), dynamic Huffman coding (LZH), and Shannon-Fano coding (ZIP 1.x)), all
  2946. of which result in a certain degree of improvement over the basic scheme,
  2947. especially when the data are rather random and the LZSS compressor has little
  2948. effect.
  2949.   Recently an algorithm was developed which combines the ideas behind LZ77 and
  2950. LZ78 to produce a hybrid called LZFG.  LZFG uses the standard sliding window,
  2951. but stores the data in a modified trie data structure and produces as output
  2952. the position of the text in the trie.  Since LZFG only inserts complete
  2953. *phrases* into the dictionary, it should run faster than other LZ77-based
  2954. compressors.
  2955.  
  2956. All popular archivers (arj, lha, zip, zoo) are variations on the LZ77 theme.
  2957.  
  2958. ------------------------------------------------------------------------------
  2959.  
  2960. Subject: [71] Introduction to MPEG (long)
  2961.  
  2962.  
  2963. For MPEG players, see item 15 in part 1 of the FAQ.  Frank Gadegast
  2964. <phade@cs.tu-berlin.de> also posts a FAQ specialized in MPEG, available in
  2965. ftp.cs.tu-berlin.de:/pub/msdos/windows3/graphics/mpegfa*.zip.
  2966. Chad Fogg <cfogg@ole.cdac.com> also has another FAQ in preparation.
  2967. The site ftp.crs4.it dedicated to the MPEG compression standard,
  2968. see the directory mpeg and subdirectories.
  2969.  
  2970.  
  2971. Introduction to MPEG written by Mark Adler <madler@cco.caltech.edu> around  
  2972. January 1992 (and hence wildly out of date in this fast moving  
  2973. area--any volunteers to update this section are welcome):
  2974.  
  2975. Q. What is MPEG?
  2976. A. MPEG is a group of people that meet under ISO (the International
  2977.    Standards Organization) to generate standards for digital video
  2978.    (sequences of images in time) and audio compression.  In particular,
  2979.    they define a compressed bit stream, which implicitly defines a
  2980.    decompressor.  However, the compression algorithms are up to the
  2981.    individual manufacturers, and that is where proprietary advantage
  2982.    is obtained within the scope of a publicly available international
  2983.    standard.  MPEG meets roughly four times a year for roughly a week
  2984.    each time.  In between meetings, a great deal of work is done by
  2985.    the members, so it doesn't all happen at the meetings.  The work
  2986.    is organized and planned at the meetings.
  2987.  
  2988. Q. So what does MPEG stand for?
  2989. A. Moving Pictures Experts Group.
  2990.  
  2991. Q. Does it have anything to do with JPEG?
  2992. A. Well, it sounds the same, and they are part of the same subcommittee
  2993.    of ISO along with JBIG and MHEG, and they usually meet at the same
  2994.    place at the same time.  However, they are different sets of people
  2995.    with few or no common individual members, and they have different
  2996.    charters and requirements.  JPEG is for still image compression.
  2997.  
  2998. Q. Then what's JBIG and MHEG?
  2999. A. Sorry I mentioned them. Ok, I'll simply say that JBIG is for binary
  3000.    image compression (like faxes), and MHEG is for multi-media data
  3001.    standards (like integrating stills, video, audio, text, etc.).
  3002.    For an introduction to JBIG, see question 74 below.
  3003.  
  3004. Q. Ok, I'll stick to MPEG.  What has MPEG accomplished?
  3005. A. So far (as of January 1992), they have completed the "Committee
  3006.    Draft" of MPEG phase I, colloquially called MPEG I.  It defines
  3007.    a bit stream for compressed video and audio optimized to fit into
  3008.    a bandwidth (data rate) of 1.5 Mbits/s.  This rate is special
  3009.    because it is the data rate of (uncompressed) audio CD's and DAT's.
  3010.    The draft is in three parts, video, audio, and systems, where the
  3011.    last part gives the integration of the audio and video streams
  3012.    with the proper timestamping to allow synchronization of the two.
  3013.    They have also gotten well into MPEG phase II, whose task is to
  3014.    define a bitstream for video and audio coded at around 3 to 10
  3015.    Mbits/s.
  3016.  
  3017. Q. So how does MPEG I work?
  3018. A. First off, it starts with a relatively low resolution video
  3019.    sequence (possibly decimated from the original) of about 352 by
  3020.    240 frames by 30 frames/s (US--different numbers for Europe),
  3021.    but original high (CD) quality audio.  The images are in color,
  3022.    but converted to YUV space, and the two chrominance channels
  3023.    (U and V) are decimated further to 176 by 120 pixels.  It turns
  3024.    out that you can get away with a lot less resolution in those
  3025.    channels and not notice it, at least in "natural" (not computer
  3026.    generated) images.
  3027.  
  3028.    The basic scheme is to predict motion from frame to frame in the
  3029.    temporal direction, and then to use DCT's (discrete cosine
  3030.    transforms) to organize the redundancy in the spatial directions.
  3031.    The DCT's are done on 8x8 blocks, and the motion prediction is
  3032.    done in the luminance (Y) channel on 16x16 blocks.  In other words,
  3033.    given the 16x16 block in the current frame that you are trying to
  3034.    code, you look for a close match to that block in a previous or
  3035.    future frame (there are backward prediction modes where later
  3036.    frames are sent first to allow interpolating between frames).
  3037.    The DCT coefficients (of either the actual data, or the difference
  3038.    between this block and the close match) are "quantized", which
  3039.    means that you divide them by some value to drop bits off the
  3040.    bottom end.  Hopefully, many of the coefficients will then end up
  3041.    being zero.  The quantization can change for every "macroblock"
  3042.    (a macroblock is 16x16 of Y and the corresponding 8x8's in both
  3043.    U and V).  The results of all of this, which include the DCT
  3044.    coefficients, the motion vectors, and the quantization parameters
  3045.    (and other stuff) is Huffman coded using fixed tables.  The DCT
  3046.    coefficients have a special Huffman table that is "two-dimensional"
  3047.    in that one code specifies a run-length of zeros and the non-zero
  3048.    value that ended the run.  Also, the motion vectors and the DC
  3049.    DCT components are DPCM (subtracted from the last one) coded.
  3050.  
  3051. Q. So is each frame predicted from the last frame?
  3052. A. No.  The scheme is a little more complicated than that.  There are
  3053.    three types of coded frames.  There are "I" or intra frames.  They
  3054.    are simply a frame coded as a still image, not using any past
  3055.    history.  You have to start somewhere.  Then there are "P" or
  3056.    predicted frames.  They are predicted from the most recently
  3057.    reconstructed I or P frame.  (I'm describing this from the point
  3058.    of view of the decompressor.)  Each macroblock in a P frame can
  3059.    either come with a vector and difference DCT coefficients for a
  3060.    close match in the last I or P, or it can just be "intra" coded
  3061.    (like in the I frames) if there was no good match.
  3062.  
  3063.    Lastly, there are "B" or bidirectional frames.  They are predicted
  3064.    from the closest two I or P frames, one in the past and one in the
  3065.    future.  You search for matching blocks in those frames, and try
  3066.    three different things to see which works best.  (Now I have the
  3067.    point of view of the compressor, just to confuse you.)  You try using
  3068.    the forward vector, the backward vector, and you try averaging the
  3069.    two blocks from the future and past frames, and subtracting that from
  3070.    the block being coded.  If none of those work well, you can intra-
  3071.    code the block.
  3072.  
  3073.    The sequence of decoded frames usually goes like:
  3074.  
  3075.    IBBPBBPBBPBBIBBPBBPB...
  3076.  
  3077.    Where there are 12 frames from I to I (for US and Japan anyway.)
  3078.    This is based on a random access requirement that you need a
  3079.    starting point at least once every 0.4 seconds or so.  The ratio
  3080.    of P's to B's is based on experience.
  3081.  
  3082.    Of course, for the decoder to work, you have to send that first
  3083.    P *before* the first two B's, so the compressed data stream ends
  3084.    up looking like:
  3085.  
  3086.    0xx312645...
  3087.  
  3088.    where those are frame numbers.  xx might be nothing (if this is
  3089.    the true starting point), or it might be the B's of frames -2 and
  3090.    -1 if we're in the middle of the stream somewhere.
  3091.  
  3092.    You have to decode the I, then decode the P, keep both of those
  3093.    in memory, and then decode the two B's.  You probably display the
  3094.    I while you're decoding the P, and display the B's as you're
  3095.    decoding them, and then display the P as you're decoding the next
  3096.    P, and so on.
  3097.  
  3098. Q. You've got to be kidding.
  3099. A. No, really!
  3100.  
  3101. Q. Hmm.  Where did they get 352x240?
  3102. A. That derives from the CCIR-601 digital television standard which
  3103.    is used by professional digital video equipment.  It is (in the US)
  3104.    720 by 243 by 60 fields (not frames) per second, where the fields
  3105.    are interlaced when displayed.  (It is important to note though
  3106.    that fields are actually acquired and displayed a 60th of a second
  3107.    apart.)  The chrominance channels are 360 by 243 by 60 fields a
  3108.    second, again interlaced.  This degree of chrominance decimation
  3109.    (2:1 in the horizontal direction) is called 4:2:2.  The source
  3110.    input format for MPEG I, called SIF, is CCIR-601 decimated by 2:1
  3111.    in the horizontal direction, 2:1 in the time direction, and an
  3112.    additional 2:1 in the chrominance vertical direction.  And some
  3113.    lines are cut off to make sure things divide by 8 or 16 where
  3114.    needed.
  3115.  
  3116. Q. What if I'm in Europe?
  3117. A. For 50 Hz display standards (PAL, SECAM) change the number of lines
  3118.    in a field from 243 or 240 to 288, and change the display rate to
  3119.    50 fields/s or 25 frames/s.  Similarly, change the 120 lines in
  3120.    the decimated chrominance channels to 144 lines.  Since 288*50 is
  3121.    exactly equal to 240*60, the two formats have the same source data
  3122.    rate.
  3123.  
  3124. Q. You didn't mention anything about the audio compression.
  3125. A. Oh, right.  Well, I don't know as much about the audio compression.
  3126.    Basically they use very carefully developed psychoacoustic models
  3127.    derived from experiments with the best obtainable listeners to
  3128.    pick out pieces of the sound that you can't hear.  There are what
  3129.    are called "masking" effects where, for example, a large component
  3130.    at one frequency will prevent you from hearing lower energy parts
  3131.    at nearby frequencies, where the relative energy vs. frequency
  3132.    that is masked is described by some empirical curve.  There are
  3133.    similar temporal masking effects, as well as some more complicated
  3134.    interactions where a temporal effect can unmask a frequency, and
  3135.    vice-versa.
  3136.  
  3137.    The sound is broken up into spectral chunks with a hybrid scheme
  3138.    that combines sine transforms with subband transforms, and the
  3139.    psychoacoustic model written in terms of those chunks.  Whatever
  3140.    can be removed or reduced in precision is, and the remainder is
  3141.    sent.  It's a little more complicated than that, since the bits
  3142.    have to be allocated across the bands.  And, of course, what is
  3143.    sent is entropy coded.
  3144.  
  3145. Q. So how much does it compress?
  3146. A. As I mentioned before, audio CD data rates are about 1.5 Mbits/s.
  3147.    You can compress the same stereo program down to 256 Kbits/s with
  3148.    no loss in discernable quality.  (So they say.  For the most part
  3149.    it's true, but every once in a while a weird thing might happen
  3150.    that you'll notice.  However the effect is very small, and it takes
  3151.    a listener trained to notice these particular types of effects.)
  3152.    That's about 6:1 compression.  So, a CD MPEG I stream would have
  3153.    about 1.25 MBits/s left for video.  The number I usually see though
  3154.    is 1.15 MBits/s (maybe you need the rest for the system data
  3155.    stream).  You can then calculate the video compression ratio from
  3156.    the numbers here to be about 26:1.  If you step back and think
  3157.    about that, it's little short of a miracle.  Of course, it's lossy
  3158.    compression, but it can be pretty hard sometimes to see the loss,
  3159.    if you're comparing the SIF original to the SIF decompressed.  There
  3160.    is, however, a very noticeable loss if you're coming from CCIR-601
  3161.    and have to decimate to SIF, but that's another matter.  I'm not
  3162.    counting that in the 26:1.
  3163.  
  3164.    The standard also provides for other bit rates ranging from 32Kbits/s
  3165.    for a single channel, up to 448 Kbits/s for stereo.
  3166.  
  3167. Q. What's phase II?
  3168. A. As I said, there is a considerable loss of quality in going from
  3169.    CCIR-601 to SIF resolution.  For entertainment video, it's simply
  3170.    not acceptable.  You want to use more bits and code all or almost
  3171.    all the CCIR-601 data.  From subjective testing at the Japan
  3172.    meeting in November 1991, it seems that 4 MBits/s can give very
  3173.    good quality compared to the original CCIR-601 material.  The
  3174.    objective of phase II is to define a bit stream optimized for these
  3175.    resolutions and bit rates.
  3176.  
  3177. Q. Why not just scale up what you're doing with MPEG I?
  3178. A. The main difficulty is the interlacing.  The simplest way to extend
  3179.    MPEG I to interlaced material is to put the fields together into
  3180.    frames (720x486x30/s).  This results in bad motion artifacts that
  3181.    stem from the fact that moving objects are in different places
  3182.    in the two fields, and so don't line up in the frames.  Compressing
  3183.    and decompressing without taking that into account somehow tends to
  3184.    muddle the objects in the two different fields.
  3185.  
  3186.    The other thing you might try is to code the even and odd field
  3187.    streams separately.  This avoids the motion artifacts, but as you
  3188.    might imagine, doesn't get very good compression since you are not
  3189.    using the redundancy between the even and odd fields where there
  3190.    is not much motion (which is typically most of image).
  3191.  
  3192.    Or you can code it as a single stream of fields.  Or you can
  3193.    interpolate lines.  Or, etc. etc.  There are many things you can
  3194.    try, and the point of MPEG II is to figure out what works well.
  3195.    MPEG II is not limited to consider only derivations of MPEG I.
  3196.    There were several non-MPEG I-like schemes in the competition in
  3197.    November, and some aspects of those algorithms may or may not
  3198.    make it into the final standard for entertainment video compression.
  3199.  
  3200. Q. So what works?
  3201. A. Basically, derivations of MPEG I worked quite well, with one that
  3202.    used wavelet subband coding instead of DCT's that also worked very
  3203.    well.  Also among the worked-very-well's was a scheme that did not
  3204.    use B frames at all, just I and P's.  All of them, except maybe one,
  3205.    did some sort of adaptive frame/field coding, where a decision is
  3206.    made on a macroblock basis as to whether to code that one as one
  3207.    frame macroblock or as two field macroblocks.  Some other aspects
  3208.    are how to code I-frames--some suggest predicting the even field
  3209.    from the odd field.  Or you can predict evens from evens and odds
  3210.    or odds from evens and odds or any field from any other field, etc.
  3211.  
  3212. Q. So what works?
  3213. A. Ok, we're not really sure what works best yet.  The next step is
  3214.    to define a "test model" to start from, that incorporates most of
  3215.    the salient features of the worked-very-well proposals in a
  3216.    simple way.  Then experiments will be done on that test model,
  3217.    making a mod at a time, and seeing what makes it better and what
  3218.    makes it worse.  Example experiments are, B's or no B's, DCT vs.
  3219.    wavelets, various field prediction modes, etc.  The requirements,
  3220.    such as implementation cost, quality, random access, etc. will all
  3221.    feed into this process as well.
  3222.  
  3223. Q. When will all this be finished?
  3224. A. I don't know.  I'd have to hope in about a year or less.
  3225.  
  3226. Q. How do I join MPEG?
  3227. A. You don't join MPEG.  You have to participate in ISO as part of a
  3228.    national delegation.  How you get to be part of the national
  3229.    delegation is up to each nation.  I only know the U.S., where you
  3230.    have to attend the corresponding ANSI meetings to be able to
  3231.    attend the ISO meetings.  Your company or institution has to be
  3232.    willing to sink some bucks into travel since, naturally, these
  3233.    meetings are held all over the world.  (For example, Paris,
  3234.    Santa Clara, Kurihama Japan, Singapore, Haifa Israel, Rio de
  3235.    Janeiro, London, etc.)
  3236.  
  3237. Q. Well, then how do I get the documents, like the MPEG I draft?
  3238. A. MPEG is a draft ISO standard. It's exact name is ISO CD 11172.
  3239.    The draft consists of three parts: System, Video, and Audio. The
  3240.    System part (11172-1) deals with synchronization and multiplexing
  3241.    of audio-visual information, while the Video (11172-2) and Audio
  3242.    part (11172-3) address the video and the audio compression techniques
  3243.    respectively.
  3244.  
  3245.    You may order it from your national standards body (e.g. ANSI in
  3246.    the USA) or buy it from companies like
  3247.      OMNICOM
  3248.      phone +44 438 742424
  3249.      FAX +44 438 740154
  3250.  
  3251. ------------------------------------------------------------------------------
  3252.  
  3253. Subject: [72] What is wavelet theory?
  3254.  
  3255.  
  3256. Preprints and software are available by anonymous ftp from the
  3257. Yale Mathematics Department computer ceres.math.yale.edu[130.132.23.22],
  3258. in pub/wavelets and pub/software.
  3259.  
  3260. epic and hcompress are wavelet coders. (For source code, see item 15
  3261. in part one).
  3262.  
  3263. Bill Press of Harvard/CfA has made some things available for anonymous
  3264. ftp on cfata4.harvard.edu [128.103.40.79] in directory /pub. There is
  3265. a short TeX article on wavelet theory (wavelet.tex, to be included in
  3266. a future edition of Numerical Recipes), some sample wavelet code
  3267. (wavelet.f, in FORTRAN - sigh), and a beta version of an astronomical
  3268. image compression program which he is currently developing (FITS
  3269. format data files only, in fitspress08.tar.Z).
  3270.  
  3271. A mailing list dedicated to research on wavelets has been set up at the
  3272. University of South Carolina. To subscribe to this mailing list, send a
  3273. message with "subscribe" as the subject to wavelet@math.scarolina.edu.
  3274.  
  3275.  
  3276. A 5 minute course in wavelet transforms, by Richard Kirk <rak@crosfield.co.uk>:
  3277.  
  3278. Do you know what a Haar transform is? Its a transform to another orthonormal
  3279. space (like the DFT), but the basis functions are a set of square wave bursts
  3280. like this...
  3281.  
  3282.    +--+                         +------+
  3283.    +  |  +------------------    +      |      +--------------
  3284.       +--+                             +------+
  3285.  
  3286.          +--+                                 +------+
  3287.    ------+  |  +------------    --------------+      |      +
  3288.             +--+                                     +------+
  3289.  
  3290.                +--+             +-------------+
  3291.    ------------+  |  +------    +             |             +
  3292.                   +--+                        +-------------+
  3293.  
  3294.                      +--+       +---------------------------+
  3295.    ------------------+  |  +    +                           +
  3296.                         +--+
  3297.  
  3298. This is the set of functions for an 8-element 1-D Haar transform. You
  3299. can probably see how to extend this to higher orders and higher dimensions
  3300. yourself. This is dead easy to calculate, but it is not what is usually
  3301. understood by a wavelet transform.
  3302.  
  3303. If you look at the eight Haar functions you see we have four functions
  3304. that code the highest resolution detail, two functions that code the
  3305. coarser detail, one function that codes the coarser detail still, and the 
  3306. top function that codes the average value for the whole `image'.
  3307.  
  3308. Haar function can be used to code images instead of the DFT. With bilevel
  3309. images (such as text) the result can look better, and it is quicker to code.
  3310. Flattish regions, textures, and soft edges in scanned images get a nasty
  3311. `blocking' feel to them. This is obvious on hardcopy, but can be disguised on
  3312. color CRTs by the effects of the shadow mask. The DCT gives more consistent
  3313. results.
  3314.  
  3315. This connects up with another bit of maths sometimes called Multispectral
  3316. Image Analysis, sometimes called Image Pyramids.
  3317.  
  3318. Suppose you want to produce a discretely sampled image from a continuous 
  3319. function. You would do this by effectively `scanning' the function using a
  3320. sinc function [ sin(x)/x ] `aperture'. This was proved by Shannon in the 
  3321. `forties. You can do the same thing starting with a high resolution
  3322. discretely sampled image. You can then get a whole set of images showing 
  3323. the edges at different resolutions by differencing the image at one
  3324. resolution with another version at another resolution. If you have made this
  3325. set of images properly they ought to all add together to give the original 
  3326. image.
  3327.  
  3328. This is an expansion of data. Suppose you started off with a 1K*1K image.
  3329. You now may have a 64*64 low resolution image plus difference images at 128*128
  3330. 256*256, 512*512 and 1K*1K. 
  3331.  
  3332. Where has this extra data come from? If you look at the difference images you 
  3333. will see there is obviously some redundancy as most of the values are near 
  3334. zero. From the way we constructed the levels we know that locally the average
  3335. must approach zero in all levels but the top. We could then construct a set of
  3336. functions out of the sync functions at any level so that their total value 
  3337. at all higher levels is zero. This gives us an orthonormal set of basis 
  3338. functions for a transform. The transform resembles the Haar transform a bit,
  3339. but has symmetric wave pulses that decay away continuously in either direction
  3340. rather than square waves that cut off sharply. This transform is the
  3341. wavelet transform ( got to the point at last!! ).
  3342.  
  3343. These wavelet functions have been likened to the edge detecting functions
  3344. believed to be present in the human retina.
  3345.  
  3346.  
  3347. Loren I. Petrich <lip@s1.gov> adds that order 2 or 3 Daubechies
  3348. discrete wavelet transforms have a speed comparable to DCT's, and
  3349. usually achieve compression a factor of 2 better for the same image
  3350. quality than the JPEG 8*8 DCT. (See item 25 in part 1 of this FAQ for
  3351. references on fast DCT algorithms.)
  3352.  
  3353. ------------------------------------------------------------------------------
  3354.  
  3355. Subject: [73] What is the theoretical compression limit?
  3356.  
  3357.  
  3358. There is no compressor that is guaranteed to compress all possible input
  3359. files. If it compresses some files, then it must enlarge some others.
  3360. This can be proven by a simple counting argument (see question 9).
  3361.  
  3362. As an extreme example, the following algorithm achieves optimal
  3363. compression for one special input file and enlarges all other files by
  3364. only one bit:
  3365.  
  3366. - if the input data is <insert your favorite one here>, output a single 0 bit
  3367. - otherwise output the bit 1 followed by the input data.
  3368.  
  3369. (You can even output an empty file in the first case if the decompressor
  3370. can detect by other means that the input is empty.)
  3371.  
  3372. The concept of theoretical compression limit is meaningful only
  3373. if you have a model for your input data. See question 70 above
  3374. for some examples of data models.
  3375.  
  3376. ------------------------------------------------------------------------------
  3377.  
  3378. Subject: [74] Introduction to JBIG
  3379.  
  3380.  
  3381. JBIG software and the JBIG specification are available on nic.funet.fi
  3382. in /pub/graphics/misc/test-images/jbig.tar.gz.
  3383.  
  3384.  
  3385. A short introduction to JBIG, written by Mark Adler <madler@cco.caltech.edu>:
  3386.  
  3387.   JBIG losslessly compresses binary (one-bit/pixel) images.  (The B stands
  3388.   for bi-level.)  Basically it models the redundancy in the image as the
  3389.   correlations of the pixel currently being coded with a set of nearby
  3390.   pixels called the template.  An example template might be the two
  3391.   pixels preceding this one on the same line, and the five pixels centered
  3392.   above this pixel on the previous line.  Note that this choice only
  3393.   involves pixels that have already been seen from a scanner.
  3394.  
  3395.   The current pixel is then arithmetically coded based on the eight-bit
  3396.   (including the pixel being coded) state so formed.  So there are (in this
  3397.   case) 256 contexts to be coded.  The arithmetic coder and probability
  3398.   estimator for the contexts are actually IBM's (patented) Q-coder.  The
  3399.   Q-coder uses low precision, rapidly adaptable (those two are related)
  3400.   probability estimation combined with a multiply-less arithmetic coder.
  3401.   The probability estimation is intimately tied to the interval calculations
  3402.   necessary for the arithmetic coding.
  3403.  
  3404.   JBIG actually goes beyond this and has adaptive templates, and probably
  3405.   some other bells and whistles I don't know about.  You can find a
  3406.   description of the Q-coder as well as the ancestor of JBIG in the Nov 88
  3407.   issue of the IBM Journal of Research and Development.  This is a very
  3408.   complete and well written set of five articles that describe the Q-coder
  3409.   and a bi-level image coder that uses the Q-coder.
  3410.  
  3411.   You can use JBIG on grey-scale or even color images by simply applying
  3412.   the algorithm one bit-plane at a time.  You would want to recode the
  3413.   grey or color levels first though, so that adjacent levels differ in
  3414.   only one bit (called Gray-coding).  I hear that this works well up to
  3415.   about six bits per pixel, beyond which JPEG's lossless mode works better.
  3416.   You need to use the Q-coder with JPEG also to get this performance.
  3417.  
  3418.   Actually no lossless mode works well beyond six bits per pixel, since
  3419.   those low bits tend to be noise, which doesn't compress at all.
  3420.  
  3421.   Anyway, the intent of JBIG is to replace the current, less effective
  3422.   group 3 and 4 fax algorithms.
  3423.  
  3424.  
  3425. Another introduction to JBIG, written by Hank van Bekkem <jbek@oce.nl>:
  3426.  
  3427.   The following description of the JBIG algorithm is derived from
  3428.   experiences with a software implementation I wrote following the
  3429.   specifications in the revision 4.1 draft of September 16, 1991. The
  3430.   source will not be made available in the public domain, as parts of
  3431.   JBIG are patented.
  3432.  
  3433.   JBIG (Joint Bi-level Image Experts Group) is an experts group of ISO,
  3434.   IEC and CCITT (JTC1/SC2/WG9 and SGVIII). Its job is to define a
  3435.   compression standard for lossless image coding ([1]). The main
  3436.   characteristics of the proposed algorithm are:
  3437.   - Compatible progressive/sequential coding. This means that a
  3438.     progressively coded image can be decoded sequentially, and the
  3439.     other way around.
  3440.   - JBIG will be a lossless image compression standard: all bits in
  3441.     your images before and after compression and decompression will be
  3442.     exactly the same.
  3443.  
  3444.   In the rest of this text I will first describe the JBIG algorithm in
  3445.   a short abstract of the draft. I will conclude by saying something
  3446.   about the value of JBIG.
  3447.  
  3448.  
  3449.   JBIG algorithm.
  3450.   --------------
  3451.  
  3452.   JBIG parameter P specifies the number of bits per pixel in the image.
  3453.   Its allowable range is 1 through 255, but starting at P=8 or so,
  3454.   compression will be more efficient using other algorithms. On the
  3455.   other hand, medical images such as chest X-rays are often stored with
  3456.   12 bits per pixel, while no distorsion is allowed, so JBIG can
  3457.   certainly be of use in this area. To limit the number of bit changes
  3458.   between adjacent decimal values (e.g. 127 and 128), it is wise to use
  3459.   Gray coding before compressing multi-level images with JBIG. JBIG
  3460.   then compresses the image on a bitplane basis, so the rest of this
  3461.   text assumes bi-level pixels.
  3462.  
  3463.   Progressive coding is a way to send an image gradually to a receiver
  3464.   instead of all at once. During sending, more detail is sent, and the
  3465.   receiver can build the image from low to high detail. JBIG uses
  3466.   discrete steps of detail by successively doubling the resolution. The
  3467.   sender computes a number of resolution layers D, and transmits these
  3468.   starting at the lowest resolution Dl. Resolution reduction uses
  3469.   pixels in the high resolution layer and some already computed low
  3470.   resolution pixels as an index into a lookup table. The contents of
  3471.   this table can be specified by the user.
  3472.  
  3473.   Compatibility between progressive and sequential coding is achieved
  3474.   by dividing an image into stripes. Each stripe is a horizontal bar
  3475.   with a user definable height. Each stripe is separately coded and
  3476.   transmitted, and the user can define in which order stripes,
  3477.   resolutions and bitplanes (if P>1) are intermixed in the coded data.
  3478.   A progressive coded image can be decoded sequentially by decoding
  3479.   each stripe, beginning by the one at the top of the image, to its
  3480.   full resolution, and then proceeding to the next stripe. Progressive
  3481.   decoding can be done by decoding only a specific resolution layer
  3482.   from all stripes.
  3483.  
  3484.   After dividing an image into bitplanes, resolution layers and
  3485.   stripes, eventually a number of small bi-level bitmaps are left to
  3486.   compress. Compression is done using a Q-coder. Reference [2]
  3487.   contains a full description, I will only outline the basic principles
  3488.   here.
  3489.  
  3490.   The Q-coder codes bi-level pixels as symbols using the probability of
  3491.   occurrence of these symbols in a certain context. JBIG defines two
  3492.   kinds of context, one for the lowest resolution layer (the base
  3493.   layer), and one for all other layers (differential layers).
  3494.   Differential layer contexts contain pixels in the layer to be coded,
  3495.   and in the corresponding lower resolution layer.
  3496.  
  3497.   For each combination of pixel values in a context, the probability
  3498.   distribution of black and white pixels can be different. In an all
  3499.   white context, the probability of coding a white pixel will be much
  3500.   greater than that of coding a black pixel. The Q-coder assigns, just
  3501.   like a Huffman coder, more bits to less probable symbols, and so
  3502.   achieves compression. The Q-coder can, unlike a Huffmann coder,
  3503.   assign one output codebit to more than one input symbol, and thus is
  3504.   able to compress bi-level pixels without explicit clustering, as
  3505.   would be necessary using a Huffman coder.
  3506.  
  3507.   Maximum compression will be achieved when all probabilities (one set
  3508.   for each combination of pixel values in the context) follow the
  3509.   probabilities of the pixels. The Q-coder therefore continuously
  3510.   adapts these probabilities to the symbols it sees.
  3511.  
  3512.  
  3513.   JBIG value.
  3514.   ----------
  3515.  
  3516.   In my opinion, JBIG can be regarded as two combined devices:
  3517.   - Providing the user the service of sending or storing multiple
  3518.     representations of images at different resolutions without any
  3519.     extra cost in storage. Differential layer contexts contain pixels
  3520.     in two resolution layers, and so enable the Q-coder to effectively
  3521.     code the difference in information between the two layers, instead
  3522.     of the information contained in every layer. This means that,
  3523.     within a margin of approximately 5%, the number of resolution
  3524.     layers doesn't effect the compression ratio.
  3525.   - Providing the user a very efficient compression algorithm, mainly
  3526.     for use with bi-level images. Compared to CCITT Group 4, JBIG is
  3527.     approximately 10% to 50% better on text and line art, and even
  3528.     better on halftones. JBIG is however, just like Group 4, somewhat
  3529.     sensitive to noise in images. This means that the compression ratio
  3530.     decreases when the amount of noise in your images increases.
  3531.  
  3532.   An example of an application would be browsing through an image
  3533.   database, e.g. an EDMS (engineering document management system).
  3534.   Large A0 size drawings at 300 dpi or so would be stored using five
  3535.   resolution layers. The lowest resolution layer would fit on a
  3536.   computer screen. Base layer compressed data would be stored at the
  3537.   beginning of the compressed file, thus making browsing through large
  3538.   numbers of compressed drawings possible by reading and decompressing
  3539.   just the first small part of all files. When the user stops browsing,
  3540.   the system could automatically start decompressing all remaining
  3541.   detail for printing at high resolution.
  3542.  
  3543.   [1] "Progressive Bi-level Image Compression, Revision 4.1", ISO/IEC
  3544.       JTC1/SC2/WG9, CD 11544, September 16, 1991
  3545.   [2] "An overview of the basic principles of the Q-coder adaptive
  3546.       binary arithmetic coder", W.B. Pennebaker, J.L. Mitchell, G.G.
  3547.       Langdon, R.B. Arps, IBM Journal of research and development,
  3548.       Vol.32, No.6, November 1988, pp. 771-726 (See also the other
  3549.       articles about the Q-coder in this issue)
  3550.  
  3551. ------------------------------------------------------------------------------
  3552.  
  3553. Subject: [75] Introduction to JPEG
  3554.  
  3555. Here is a brief overview of the inner workings of JPEG, plus some
  3556. references for more detailed information, written by Tom Lane
  3557. <tgl+@cs.cmu.edu>.  Please read item 19 in part 1 first.
  3558.  
  3559. JPEG works on either full-color or gray-scale images; it does not handle
  3560. bilevel (black and white) images, at least not efficiently.  It doesn't
  3561. handle colormapped images either; you have to pre-expand those into an
  3562. unmapped full-color representation.  JPEG works best on "continuous tone"
  3563. images; images with many sudden jumps in color values will not compress well.
  3564.  
  3565. There are a lot of parameters to the JPEG compression process.  By adjusting
  3566. the parameters, you can trade off compressed image size against reconstructed
  3567. image quality over a *very* wide range.  You can get image quality ranging
  3568. from op-art (at 100x smaller than the original 24-bit image) to quite
  3569. indistinguishable from the source (at about 3x smaller).  Usually the
  3570. threshold of visible difference from the source image is somewhere around 10x
  3571. to 20x smaller than the original, ie, 1 to 2 bits per pixel for color images.
  3572. Grayscale requires a little bit less space.
  3573.  
  3574. JPEG defines a "baseline" lossy algorithm, plus optional extensions for
  3575. progressive and hierarchical coding.  There is also a separate lossless
  3576. compression mode; this typically gives about 2:1 compression, ie about 12
  3577. bits per color pixel.  Most currently available JPEG hardware and software
  3578. handles only the baseline mode.
  3579.  
  3580.  
  3581. Here's the outline of the baseline compression algorithm:
  3582.  
  3583. 1. Transform the image into a suitable color space.  This is a no-op for
  3584. grayscale, but for color images you generally want to transform RGB into a
  3585. luminance/chrominance color space (YCbCr, YUV, etc).  The luminance component
  3586. is grayscale and the other two axes are color information.  The reason for
  3587. doing this is that you can afford to lose a lot more information in the
  3588. chrominance components than you can in the luminance component; the human eye
  3589. is not as sensitive to high-frequency color info as it is to high-frequency
  3590. luminance.  (See any TV system for precedents.)  You don't have to change the
  3591. color space if you don't want to, as the remainder of the algorithm works on
  3592. each color component independently, and doesn't care just what the data is.
  3593. However, compression will be less since you will have to code all the
  3594. components at luminance quality.
  3595.  
  3596. 2. (Optional) Downsample each component by averaging together groups of
  3597. pixels.  The luminance component is left at full resolution, while the color
  3598. components are usually reduced 2:1 horizontally and either 2:1 or 1:1 (no
  3599. change) vertically.  In JPEG-speak these alternatives are usually called
  3600. 2h2v and 2h1v sampling, but you may also see the terms "411" and "422"
  3601. sampling.  This step immediately reduces the data volume by one-half or
  3602. one-third, while having almost no impact on perceived quality.  (Obviously
  3603. this would not be true if you tried it in RGB color space...)  Note that
  3604. downsampling is not applicable to gray-scale data.
  3605.  
  3606. 3. Group the pixel values for each component into 8x8 blocks.  Transform each
  3607. 8x8 block through a discrete cosine transform (DCT); this is a relative of the
  3608. Fourier transform and likewise gives a frequency map, with 8x8 components.
  3609. Thus you now have numbers representing the average value in each block and
  3610. successively higher-frequency changes within the block.  The motivation for
  3611. doing this is that you can now throw away high-frequency information without
  3612. affecting low-frequency information.  (The DCT transform itself is reversible
  3613. except for roundoff error.)  See question 25 for fast DCT algorithms.
  3614.  
  3615. 4. In each block, divide each of the 64 frequency components by a separate
  3616. "quantization coefficient", and round the results to integers.  This is the
  3617. fundamental information-losing step.  A Q.C. of 1 loses no information;
  3618. larger Q.C.s lose successively more info.  The higher frequencies are normally
  3619. reduced much more than the lower.  (All 64 Q.C.s are parameters to the
  3620. compression process; tuning them for best results is a black art.  It seems
  3621. likely that the best values are yet to be discovered.  Most existing coders
  3622. use simple multiples of the example tables given in the JPEG standard.)
  3623.  
  3624. 5. Encode the reduced coefficients using either Huffman or arithmetic coding.
  3625. (Strictly speaking, baseline JPEG only allows Huffman coding; arithmetic
  3626. coding is an optional extension.)   Notice that this step is lossless, so it
  3627. doesn't affect image quality.  The arithmetic coding option uses Q-coding;
  3628. it is identical to the coder used in JBIG (see question 74).  Be aware that
  3629. Q-coding is patented.  Most existing implementations support only the Huffman
  3630. mode, so as to avoid license fees.  The arithmetic mode offers maybe 5 or 10%
  3631. better compression, which isn't enough to justify paying fees.
  3632.  
  3633. 6. Tack on appropriate headers, etc, and output the result.  In an
  3634. "interchange" JPEG file, all of the compression parameters are included
  3635. in the headers so that the decompressor can reverse the process.  For
  3636. specialized applications, the spec permits the parameters to be omitted
  3637. from the file; this saves several hundred bytes of overhead, but it means
  3638. that the decompressor must know what parameters the compressor used.
  3639.  
  3640.  
  3641. The decompression algorithm reverses this process, and typically adds some
  3642. smoothing steps to reduce pixel-to-pixel discontinuities.
  3643.  
  3644.  
  3645. Extensions:
  3646.  
  3647. The progressive mode is intended to support real-time transmission of images.
  3648. It allows the DCT coefficients to be sent incrementally in multiple "scans"
  3649. of the image.  With each scan, the decoder can produce a higher-quality
  3650. rendition of the image.  Thus a low-quality preview can be sent very quickly,
  3651. then refined as time allows.  Notice that the decoder must do essentially a
  3652. full JPEG decode cycle for each scan, so this scheme is useful only with fast
  3653. decoders (meaning dedicated hardware, at least at present).  However, the
  3654. total number of bits sent can actually be somewhat less than is necessary in
  3655. the baseline mode, especially if arithmetic coding is used.  So progressive
  3656. coding might be useful even if the decoder will simply save up the bits and
  3657. make only one output pass.
  3658.  
  3659. The hierarchical mode represents an image at multiple resolutions.  For
  3660. example, one could provide 512x512, 1024x1024, and 2048x2048 versions of the
  3661. image.  The higher-resolution images are coded as differences from the next
  3662. smaller image, and thus require many fewer bits than they would if stored
  3663. independently.  (However, the total number of bits will be greater than that
  3664. needed to store just the highest-resolution frame.)  Note that the individual
  3665. frames in a hierarchical sequence may be coded progressively if desired.
  3666.  
  3667.  
  3668. Lossless JPEG:
  3669.  
  3670. The separate lossless mode does not use DCT, since roundoff errors prevent a
  3671. DCT calculation from being lossless.  For the same reason, one would not
  3672. normally use colorspace conversion or downsampling, although these are
  3673. permitted by the standard.  The lossless mode simply codes the difference
  3674. between each pixel and the "predicted" value for the pixel.  The predicted
  3675. value is a simple function of the already-transmitted pixels just above and
  3676. to the left of the current one (eg, their average; 8 different predictor
  3677. functions are permitted).  The sequence of differences is encoded using the
  3678. same back end (Huffman or arithmetic) used in the lossy mode.
  3679.  
  3680. The main reason for providing a lossless option is that it makes a good
  3681. adjunct to the hierarchical mode: the final scan in a hierarchical sequence
  3682. can be a lossless coding of the remaining differences, to achieve overall
  3683. losslessness.  This isn't quite as useful as it may at first appear, because
  3684. exact losslessness is not guaranteed unless the encoder and decoder have
  3685. identical IDCT implementations (ie identical roundoff errors).
  3686.  
  3687.  
  3688. References:
  3689.  
  3690. For a good technical introduction to JPEG, see:
  3691.     Wallace, Gregory K.  "The JPEG Still Picture Compression Standard",
  3692.     Communications of the ACM, April 1991 (vol. 34 no. 4), pp. 30-44.
  3693. (Adjacent articles in that issue discuss MPEG motion picture compression,
  3694. applications of JPEG, and related topics.)  If you don't have the CACM issue
  3695. handy, a PostScript file containing a revised version of this article is
  3696. available at ftp.uu.net, graphics/jpeg/wallace.ps.Z.  The file (actually a
  3697. preprint for an article to appear in IEEE Trans. Consum. Elect.) omits the
  3698. sample images that appeared in CACM, but it includes corrections and some
  3699. added material.  Note: the Wallace article is copyright ACM and IEEE, and
  3700. it may not be used for commercial purposes.
  3701.  
  3702. An alternative, more leisurely explanation of JPEG can be found in "The Data
  3703. Compression Book" by Mark Nelson ([Nel 1991], see question 7).  This book
  3704. provides excellent introductions to many data compression methods including
  3705. JPEG, plus sample source code in C.  The JPEG-related source code is far from
  3706. industrial-strength, but it's a pretty good learning tool.
  3707.  
  3708. An excellent textbook about JPEG is "JPEG Still Image Data Compression
  3709. Standard" by William B. Pennebaker and Joan L. Mitchell.  Published by Van
  3710. Nostrand Reinhold, 1993, ISBN 0-442-01272-1.  650 pages, price US$59.95.
  3711. (VNR will accept credit card orders at 800/842-3636, or get your local
  3712. bookstore to order it.)  This book includes the complete text of the ISO
  3713. JPEG standards, DIS 10918-1 and draft DIS 10918-2.  Review by Tom Lane:
  3714. "This is by far the most complete exposition of JPEG in existence.  It's
  3715. written by two people who know what they are talking about: both serve on the
  3716. ISO JPEG standards committee.  If you want to know how JPEG works or why it
  3717. works that way, this is the book to have."
  3718.  
  3719. There are a number of errors in the first printing of the Pennebaker
  3720. & Mitchell book.  An errata list is available at ftp.uu.net:
  3721. graphics/jpeg/pm.errata.  At last report, all were fixed in the
  3722. second printing.
  3723.  
  3724. The official specification of JPEG is not currently available on-line.
  3725. I hear that CCITT specs may be on-line sometime soon, which would change this.
  3726. At the moment, your best bet is to buy the Pennebaker and Mitchell textbook.
  3727.  
  3728.  
  3729. ------------------------------------------------------------------------------
  3730.  
  3731. Subject: [76] What is Vector Quantization?
  3732.  
  3733. Some vector quantization software for data analysis that is available
  3734. from cochlea.hut.fi (130.233.168.48) in the /pub directory.  One
  3735. package is lvq_pak and one is som_pak (som_pak generates Kohonen maps
  3736. of data using lvq to cluster it).
  3737.  
  3738.  
  3739. A short introduction to Vector Quantization, written by Alex Zatsman
  3740. <alex.zatsman@analog.com>:
  3741.  
  3742. In Scalar  Quantization one represents  the values by  fixed subset of
  3743. representative values. For  examples, if you  have  16 bit  values and
  3744. send  only 8 most  signifcant bits, you  get an  approximation  of the
  3745. original data  at  the expense of  precision.  In this case  the fixed
  3746. subset is all the 16-bit numbers divisable by 256, i.e 0, 256, 512,...
  3747.  
  3748. In  Vector Quantization  you   represent   not individual values   but
  3749. (usually small) arrays of them. A typical  example  is a color  map: a
  3750. color picture can  be  represented by  a  2D array  of  triplets  (RGB
  3751. values). In most pictures  those triplets do  not cover the  whole RGB
  3752. space but  tend to   concetrate  in certain   areas. For  example, the
  3753. picture of a forest will typically have a lot of green. One can select
  3754. a relatively  small  subset (typically 256 elements) of representative
  3755. colors, i.e RGB  triplets,  and then approximate  each  triplet by the
  3756. representative of  that small set. In case  of 256 one  can use 1 byte
  3757. instead of 3 for each pixel.
  3758.  
  3759. One  can do   the  same   for  any large  data  sets,  especialy  when
  3760. consecutive points are correlated in some way. CELP speech compression
  3761. algorithms  use  those subsets  "codebooks" and   use them to quantize
  3762. exciation vectors  for linear prediction  -- hence the name CELP which
  3763. stands for Codebook Excited Linear Prediction.  (See item 26 in part 1
  3764. of this FAQ for more information about CELP.)
  3765.  
  3766. Note that Vector Quantization, just like Scalar Quantization, is a lossy
  3767. compression.
  3768.  
  3769.  
  3770. Article: 9670 of comp.compression
  3771. Path: chorus!chorus.fr
  3772. From: jloup@chorus.fr (Jean-loup Gailly)
  3773. Newsgroups: comp.compression,comp.compression.research,news.answers,comp.answers
  3774. Subject: comp.compression Frequently Asked Questions (part 3/3)
  3775. Summary: *** READ THIS BEFORE POSTING ***
  3776. Keywords: data compression, FAQ
  3777. Message-ID: <compr3_21feb94@chorus.fr>
  3778. Date: 21 Feb 94 16:54:44 GMT
  3779. Expires: 30 Mar 94 16:17:20 GMT
  3780. References: <compr1_21feb94@chorus.fr> <compr2_21feb94@chorus.fr>
  3781. Sender: news@chorus.chorus.fr
  3782. Reply-To: jloup@chorus.fr
  3783. Followup-To: comp.compression
  3784. Lines: 573
  3785. Approved: news-answers-request@MIT.Edu
  3786. Supersedes: <compr3_17jan94@chorus.fr>
  3787. Xref: chorus comp.compression:9670 comp.compression.research:1191 news.answers:17960 comp.answers:3825
  3788.  
  3789. Archive-name: compression-faq/part3
  3790. Last-modified: Nov 16th, 1993
  3791.  
  3792. This file is part 3 of a set of Frequently Asked Questions for the
  3793. groups comp.compression and comp.compression.research.
  3794. If you did not get part 1 or 2, you can get them by ftp
  3795. on rtfm.mit.edu in directory
  3796.    /pub/usenet/news.answers/compression-faq
  3797.  
  3798. If you don't want to see this FAQ regularly, please add the subject
  3799. line to your kill file. If you have corrections or suggestions for
  3800. this FAQ, send them to Jean-loup Gailly <jloup@chorus.fr>.  Thank you.
  3801.  
  3802. Contents
  3803. ========
  3804.  
  3805. Part 3: (Long) list of image compression hardware
  3806.  
  3807. [85] Image compression hardware
  3808. [99] Acknowledgments
  3809.  
  3810.  
  3811. Search for "Subject: [#]" to get to question number # quickly. Some news
  3812. readers can also take advantage of the message digest format used here.
  3813.  
  3814. ------------------------------------------------------------------------------
  3815.  
  3816. Subject: [85] Image compression hardware
  3817.  
  3818. Here is a list of sources of image compression hardware (JPEG, MPEG,
  3819. H.261 and others), reposted with the author's permission.  The list is
  3820. probably a little dated already, but it is a good starting point for
  3821. seeking compression chips. (Please send corrections/additions to
  3822. jloup@chorus.fr). References are taken from:
  3823.  
  3824.    VIDEO COMPRESSION OPTIONS, IEEE CICC 6-May-92
  3825.    John J. Bloomer, jbloomer@crd.ge.com, Fathy F. Yassa, Aiman A. Abdel-Malek
  3826.    General Electric Corporate R&D, KWC317 Signals and Systems Laboratory
  3827.    PO Box 8, Schenectady NY, 12301
  3828.  
  3829. (Too many people have sent comments, corrections or additions so I am
  3830. just making a common acknowledgment here.)
  3831.  
  3832.  
  3833.  Pipelined Processors, Building Blocks (Chip Sets)
  3834.  -------------------------------------------------
  3835.  
  3836. STI3200, IMSA121, STI3208 - SGS-Thompson DCT processors.  602-867-6279
  3837.     - 3200 has multiple block size options, DC to 13.5 MHz
  3838.     - A121 8x8 fixed blocks, DC to 20MHz, add/sub loop, CCITT compatible
  3839.     - 3208 8x8 fixed blocks, DC to 40MHz, CCITT compatible at 20MHz
  3840.  
  3841. STI3220 - SGS-Thompson motion estimator (H.261, MPEG).  602-867-6279
  3842.     - 8-bit input pixels, 4-bit H and V vectors out
  3843.     - adjustable block size matcher (8x8, 8x16, 16x16)
  3844.     - +7/-8 search window
  3845.     - 5V, 2W at 18MHz (max), 68 pin PLCC
  3846.  
  3847. L64765 , L64735 , L64745 - 3-chip LSI Logic JPEG set.  408-433-4383
  3848.     - L64765 raster-to-block and color-space converter, jointly developed
  3849.           with Rapid Tech.
  3850.     - L64735 block DCT processor
  3851.     - L64745 JPEG coder support, stand-alone lossless DPCM codec, dynamic
  3852.           Huffman
  3853.     - 27 MB/s on CCIR601 frames
  3854.     - minimal support logic, color and gray scale
  3855.     - 68-pin PGA or PLCC, 27 and 20 MHz versions
  3856.  
  3857. L647*0 and L6471* families - LSI Logic H.621/MPEG pieces.  408-433-8000
  3858.     - L64720 motion estimator, 30/40MHz, 8x8, 16x16 blocks, 32x32 or 16x16 
  3859.           search window, 68-pin CPGA or PPGA
  3860.     - L64730 & 735 8x8 DCT processors (12 & 8-9 bits)
  3861.     - L64740 8x8 block quantization
  3862.     - L64760 intra/inter-frame coding decision
  3863.     - L64715 BCH error correction
  3864.     - L64750/L64751 variable length encode/decode (H.261-specific)
  3865.  
  3866. ZR36020 and ZR36031 - Zoran DCT processor & quantization/encoding. 408-986-1314
  3867.     - JPEG-like scheme using 16-bit, two's complement fixed point
  3868.           arithmetic
  3869.     - includes bit-rate controls for constant # of pictures per card
  3870.     - 7.4 MHz, < 1W, 20mW in standby mode, 7.5 frames/s (f/s)
  3871.     - 36020 - 44-pin plastic quad flatpack (PQFP) or 48-pin ceramic DIP
  3872.     - 36031 - 100-pin PQFP or 85-pin PGA.
  3873.     - co-developments with Fuji Photo Film Co. Ltd. digital IC-card
  3874.           camera market
  3875.  
  3876.     Does 2-passes of image: generate histogram for optimum Huffman
  3877.     tables and quantization compute step size (ala H.261 and
  3878.     MPEG-I) for each macroblock or minimum coded unit (MCU).
  3879.  
  3880.     JPEG-compatible codec expected soon.
  3881.  
  3882. LDM3104  - Olympus DCT coefficient encoder
  3883.     - constant rate, digital IC-card camera market
  3884.     - 750 mW, 25 mW standby, 100-poin QFP
  3885.  
  3886. TMC2312 - TRW quantizer/Huffman encoder, TMC2313 Huffman decoder/dequantizer
  3887.  
  3888. TMC2311 - TRW CMOS Fast Cosine Transform Processor.  
  3889.     - 12 Bits, 15 M pixels/s
  3890.     - complies with the CCITT SGXV ( e.g. JPEG, H.261 and MPEG )
  3891.     - includes an adder-subtractor for linear predictive coding
  3892.  
  3893. MN195901 - Matsushita Electric Industrial Co.   See ISSCC 1992
  3894.     - 16-bit, 60 MIP video signal processor
  3895.     - 25 uS instruction processing
  3896.     - on-board DCT and absolute differencing
  3897.     - Philips Signetics US fab.
  3898.  
  3899. HGCT - Ricoh CRC, Generalized Chen Transform demonstration chip.  408-281-1436
  3900.     - 2D JPEG/MPEG/H.261 compatible DCT
  3901.     - includes quantization
  3902.     - 30MHz, 15K gates
  3903.     - licensing possible
  3904.  
  3905. GCTX64000 - Graphic Communication Technology Corp. chipset
  3906.     - provides CCITT H.261
  3907.     - VLSI Technology and Hitachi supply H.261 codec core. 1 micron CMOS.
  3908.  
  3909. BT - British Telecommunications  plc., Martlesham labs designed
  3910.     - H.261 codec chipset, Motorola fab.
  3911.     - 13 chips total for codec.
  3912.  
  3913.  
  3914.  Pipelined Processors, Monolithic, Programmable
  3915.  ----------------------------------------------
  3916.  
  3917. Vision Processor - Integrated Information Technology Inc. 408-727-1885
  3918.     - generic DCT, motion compensated & entropy coding codec
  3919.     - microcode for still- and motion-video compression (JPEG, H.261 and
  3920.           MPEG1)
  3921.     - 1 micron CMOS, 20 MHz and 33 MHz, PGA and 84-pin QFP  
  3922.     - JPEG only and JPEG/H/261/MPEG versions available, H.261 at 30 f/s.  
  3923.     - used by Compression Labs, Inc. CDV teleconferencing system
  3924.     - rumored to be the heart of the AT&T picture phone
  3925.  
  3926. MN195901 - Matsushita Electric Industrial Corp
  3927.     - 40 MHz DSP, built-in DCT
  3928.     - 16-bit fixed-point
  3929.  
  3930. AVP1000 -  AT&T  JPEG, MPEG and H.261 codec chipset.  800-372-2447
  3931.     - 1400D decoder, 1400C system controller
  3932.     - 1300E H.261 (CIF, QCIF, CIF240) at 30 f/s, I-frame only MPEG.
  3933.     - 1400E is superset of 1300E, motion with 1/2 pixel resolution over +/-
  3934.           32 pixels
  3935.     - YCbCr video or digital input, on-board rate FIFOs, external RAM
  3936.           required
  3937.     - 0.75 micron, 50 MHz CMOS
  3938.  
  3939.     AVP1000 is from AT&T Microelectronics.  The AT&T chip set
  3940.     handles MPEG-1, H.261, and JPEG.  1400D has on board color
  3941.     space convertor.  Limited to 4Mb/s coded rate.  The DSP does
  3942.     the MUSICAM decoding (up to layer II ?)
  3943.  
  3944.  
  3945. 82750PB, 82750DB - Intel DVI  pixel and display YUV color space processors.
  3946.     - proprietary machine code employed for compression
  3947.     - usable for other algorithms (e.g., JPEG, H.261 or MPEG1 at reduced
  3948.           data rates)
  3949.  
  3950.  
  3951.  Pipelined Processors, Monolithic, Fixed Lossless - Entropy Coders, DPCM, VQ
  3952.  ---------------------------------------------------------------------------
  3953.  
  3954. DCP - Integrated Information Tech. Inc. Data Compressor Processor  408-727-1885
  3955.     - LZ codec with on-chip dictionary store
  3956.     - on-chip buffers supporting block moves
  3957.     - targeting disk drives and network controller markets
  3958.     - 3.3V, 84-pin PQFP
  3959.  
  3960. Mystic - HP's DC-LZ codec.  408-749-9500
  3961.  
  3962. AHA3210 - Advanced Hardware Architectures DC-LZ codec. 208-883-8000
  3963.     - two independent DMA ports for 10 MB/s compress, decompress &
  3964.           pass-thru
  3965.     - addressing allows up to 16 MB record compression
  3966.     - 20 MHz internal clock, 200 mW, 100-pin PQFP
  3967.     - interface to AHA5101/5121 QIC tape controller/formatter
  3968.     - HP licensee
  3969.  
  3970. AHA3xxx/xxy - Rice (UNC) algorithm, 20M samples/sec, 4 to 14 bits. 208-883-8000
  3971.  
  3972. CRM1000 - CERAM Inc. entropy codec, proprietary algorithm.  719-540-8500
  3973.  
  3974. Rice - UNC algorithm prototype, 180 Mb/s.  See IEEE CICC 1992
  3975.     - other CICC 1992 papers:
  3976.        +JS.E. Kerneny et.al. differential read, pyramidal output CCD
  3977.          + A. Aggoun et.al. DPCM processing
  3978.  
  3979. DCD - Philips Data Compressor Decompressor IC. 914-945-6000
  3980.     - See CICC 1990 proceedings, H. Blume, et.al.
  3981.     - LZ codec, 20 MHz clock
  3982.     - Internal FIFOs, separate input/output buses, max 10 Mword/s data in
  3983.     - 5 V CMOS, 175-pin PGA
  3984.  
  3985. 9705 - Second generation Stac Electronics accelerator chip.  619-431-7474
  3986.     - Stacker LZA compression scheme(LZ-based)
  3987.     - compress at approx. 2.5 MB/s, decompress at 6 MB/s (39+ faster than
  3988.           9704)
  3989.     - standby mode 300uA
  3990.     - embedded in tapes and disks (e.g., QIC-122 Ten X Technology
  3991.           512-346-8360)
  3992.     - file compression board & software:
  3993.         + for the PC/AT - from Stac
  3994.         + for the Macintosh - from Sigma Design 415-770-0100 (40 MHz 9703)
  3995.     - InfoChip Systems Inc. - proprietary string-matching technology
  3996.           408-727-0514
  3997.  
  3998. VCEP or OTI95C71/Am95C71 - Oak Technology Inc. 408-737-0888
  3999.     - AMD CCITT B&W fax image compression
  4000.  
  4001.  
  4002.  Pipelined Processors, Monolithic, Fixed Lossy
  4003.  ---------------------------------------------
  4004.  
  4005. MB86356B - Fujitsu LTD.
  4006.     - JPEG DIS 10918-1 baseline  codec
  4007.     - on-chip quantizer tables
  4008.     - 2.5M pixel/sec input, up to 10MB/sec output
  4009.     - supports progressive and DPCM lossless modes 
  4010.     - 135 pin PGA.
  4011.  
  4012. CL550-30 - C-Cube Microsystems 408-944-8103, literature@c-cube.com
  4013.     - JPEG-8-R2 compliant baseline codec
  4014.     - 350-level pipeline, on-chip Huffman and quantizer table
  4015.     - 44.1 MB/sec (15 MB/sec for -10)
  4016.     - RGB, YUV, CMYK supported, CCIR 601 in real-time
  4017.     - 16/32-bit host interface 
  4018.     - 144 pin PGA or QFP, 2.5W at 29.41 MHz
  4019.  
  4020.     Limited to 2MB/sec (15Mb/s) coded rate.  35MHz PGA version
  4021.     available.  2:1 horizontal filter, on board programmable color
  4022.     space convertor.  Allows on pair of quantization tables to be
  4023.     loaded while other pair is used to code or decode data stream.
  4024.     Needs maintanence by host.
  4025.  
  4026. STI140 - SGS-Thompson JPEG baseline codec.  617-259-0300 [** Now cancelled **]
  4027.     - see CICC 1991 proceedings, M. Bolton.
  4028.     - 20 Mpixel/sec input, up to 20 MB/sec output
  4029.     - supports 24-bit color, 8-bit grey and 12-bit extended pixels
  4030.     - on chip Huffman and quantizer tables
  4031.     - 144 pin PQFP, 5V, < 2W., 10mW power-down mode
  4032.     - 1.2 micron, 3-layer metal CMOS, 20 MHz.    `
  4033.  
  4034. UVC7710 - UVC Corp. Integrated Multimedia Processor. Was 714-261-5336, out
  4035.           of business now.
  4036.     - proprietary, patented intra-frame compression, on-chip code tables
  4037.     - 20-35:1, 12.5 Mpixels/sec., compressed audio
  4038.     - includes much of the PC-AT (16-bit ISA) bus interface logic
  4039.     - 128 pin PJQFP plastic
  4040.  
  4041. CL950 - C-Cube/JVC implementation of the MPEG-JVC or extended mode MPEG2 
  4042.         announced.  6-9 Mb/sec.
  4043.  
  4044.     JVC mode is not MPEG-II compliant (there isn't an MPEG2 standard yet)
  4045.     but is an extension of MPEG1 at a higher rate plus interlace video
  4046.     handling.
  4047.  
  4048. CL450 - Announced June 1992.  Scaled down version of CL950, with 3Mb/sec
  4049.         limit.  Does not code or decode JPEG, only MPEG-I decoding.
  4050.  
  4051. CD-I - ASICs planned for CD-ROM, Compact Disk-Interactive defacto standards
  4052.     - CD-ROM XA - Sony-Philips-Motorola-Microsoft
  4053.     - CDTV -  Commodore.  YUV processing.
  4054.     - audio ADPCM encode/decode PC/AT boards available from Sony
  4055.           408-432-0190
  4056.  
  4057. Motorola MCD250 Full Motion Video Decoder.   512-928-5053.
  4058.     This is a CD-I MPEG Video decoder which requires only a single
  4059.     4Mbit DRAM for FMV decoding. Decodes System and Video Layers
  4060.     at up to 5Mbits/sec, converts from 24/25/30 fps IPB streams to
  4061.     25/30 fps output video in 24bit RGB/YUV format. Supports extra
  4062.     CD-I functions such as windowing and still picture mode.
  4063.     Targetted at low cost consumer applications such as CD-I,
  4064.     CD-Karaoke, Video-CD and cable TV.
  4065.  
  4066. Motorola MCD260 MPEG Audio Host Interface and DSP56001-33.  512-928-5053.
  4067.     The MCD260 is a low cost interface IC which goes between a 68K
  4068.     bus and a DSP56K and strips out the MPEG System Layer whilst also
  4069.     buffering and synchronising. A 33MHz 56001 with 8Kwords of DSPRAM
  4070.     decodes the MPEG Audio (Layer 1/II @ 44.1KHz, all modes and bit rates)
  4071.  
  4072.  
  4073.  Codecs Chips Under Development
  4074.  ------------------------------
  4075.  
  4076. MPEG1 codec chips due from - TI, Brooktree, Cypress Semiconductor, Motorola 
  4077. (successor to the DSP96002 Multimedia Engine), Xing Technology/Analog Devices, 
  4078. Sony and C-Cube
  4079.  
  4080.  
  4081. Windbond Electronics Corp. is developing a DSP chip for CD-I, MPEG and JPEG
  4082.  
  4083.  
  4084.  Using these Chips: Board Level Compression Hardware
  4085.  ------------------------------------------------------
  4086.  
  4087. + JPEG Using CL550
  4088.  
  4089. + JPEG Using Other Chip Sets
  4090.  
  4091. + DSP Chip Based JPEG/MPEG Solutions
  4092.  
  4093. + Integrated Compressed Digital Video Boards 
  4094.  
  4095.  
  4096.  JPEG Using CL550
  4097.  ---------------
  4098. C-Cube - 408-944-6300 ISA and NuBus boards 
  4099.     - for development and limited time-constraint applications
  4100.     - 1-2.5 MB/sec host bus constraints
  4101.     - Image Compression Interface (ISI) software for 3rd party CL550
  4102.           integration
  4103.  
  4104. VideoSpigot/SuperSqueeze - SuperMac Technology  408 541-6100
  4105.     - a CL550A on a NuBus board
  4106.     - 24 frame/s with CD-quality audio
  4107.     - reads from Winchester and magneto-optic drives
  4108.  
  4109. Fluency VSA-1000 - Fluent Machines, Inc. AT board set.  508 626-2144
  4110.     - compress/decompress real-time synced audio & video to a i386 PC
  4111.           Winchester
  4112.     - NTSC or PAL input, 320x240 pixels saved
  4113.     - uses i960 chip, no additional boards needed
  4114.     - M/S Windows support, 3rd party S/W (e.g., AimTech 603-883-0220)
  4115.  
  4116. Super Motion Compression - New Media Graphics  PC/AT board.  800 288-2207
  4117.     - 8Khz, 8-bit compressed audio
  4118.     - 30 f/s JPEG to & from disk
  4119.     - earlier reports: still-frame compression in several seconds per MB
  4120.  
  4121.  
  4122. Leadview  - Lead Tech Inc. AT board uses the CL550 to compress/decompress
  4123.             JFIF or JTIF format files
  4124.  
  4125. Monalisa - Opta Inc. AT board uses the CL550
  4126.  
  4127. Squeeze - Rapid Technology AT board
  4128.     - Integrated by a number of vendors into 3rd party multimedia,
  4129.           video-editing PC stations
  4130.  
  4131. Parallax Graphics - SBus, VME and PC-AT boards.  408-727-2220 or
  4132.           info@parallax.com
  4133.  
  4134. Chips and Technologies - JPEG development kit due.
  4135.  
  4136. Image Manipulation Systems, Inc - SBus compression/framebuffer/video I/O boards
  4137.     800-745-5602 or imsinfo%thumper@src.honeywell.com
  4138.  
  4139.  
  4140.  JPEG Using Other Chipsets
  4141.  -------------------------
  4142.  
  4143. Visionary - Rapid Technology JPEG AT board.  716-833-8534
  4144.     -  LSI Logic JPEG chips L647-35, -45 & -65
  4145.     - 30 f/s motion JPEG
  4146.     - 256x240 pixel compression and display from CCIR-601 input
  4147.     - private codec-frame buffer bus
  4148.     - also integrated with TrueVision multimedia hardware
  4149.  
  4150. Media 100  - Data Translation nonlinear video production system for the
  4151.           Macintosh  (QuickTime).  22 MB/s (PAL) and 18MB/s (NTSC) throughput.
  4152.  
  4153. Alice - Telephoto Communications Inc. 619-452-0903
  4154.     - Alice-H350 (PC/AT) and -H365 (PS/2) codec boards
  4155.     - use a 40 MHz TMS320C51 DSP and a IMSA121 DCT processor chip
  4156.     - JPEG (lossy and lossless), CCITT G3/G4, color and grey-scale images
  4157.  
  4158. Xing Technology - Hardware accelerator.  805-473-0145
  4159.     - compatible with their VT-Express JPEG Turbo Accelerator Software
  4160.  
  4161. Video/1 - PsiTech Inc. 714-968-7818
  4162.     - includes a 6U VME/VSB JPEG Processing Card 
  4163.     - compresses RS-170, NTSC, PAL or Secam video into 8 MB of on-board RAM
  4164.  
  4165.  
  4166.  DSP Chip Based JPEG/MPEG Solutions
  4167.  ----------------------------------
  4168.  
  4169. Optipac - Optivision Inc. PC/AT, ISA & VME codecs.  800-562-8934
  4170.     - JPEG (lossless and lossy), CCITT III/IV
  4171.     - 1 to 5 TMS32C025s
  4172.     - 512x400x16-bit images in < 1 sec.
  4173.  
  4174. XCeed ICDP-II - Micron Technology Inc. NuBus card
  4175.     - uses two AT&T Microelectronics DSP-16 DSP chips
  4176.     - driven by Storm Technologies PicturePress software
  4177.     - executes an enhanced JPEG algorithm at near-realtime.
  4178.  
  4179. PicturePress Accelerator - Storm Technology 415-691-1111 (see above)
  4180.     - also has a line of VME compression boards
  4181.     - Micro Dynamics Ltd. imaging systems use Storm accelerator
  4182.           301-589-6300
  4183.  
  4184. Picture Packer Accelerator - Video & Image Compression Corp.
  4185.     - AT and NuBus boards use the JPEG Open Standard and a TMS320C25
  4186.  
  4187. VideoPix - Software JPEG boards are offered by Sun Microsystems (S-Bus).
  4188.  
  4189. Phoenix System - T/one Inc. uses an Optivision Optipac 3250 to talk to a Storm 
  4190.                  Technologies NuBus PicturePress Accelerator to talk JPEG over 
  4191.                  analog phone lines.
  4192.  
  4193. Nextdimension - NeXt Computer Inc. 415-780-3912
  4194.     - 24+8-bit alpha, 640x480, 30 f/s decompression
  4195.     - CL550 version not shipping as announced. 
  4196.  
  4197. Spirit-40  - Sonitech International Inc. ISA card. 617-235-6824
  4198.     - two TMS320C40 DSPs for 80 MFLOPS
  4199.     - connect 16 boards in a hypercube for up to 1280 MFLOPS
  4200.     - JPEG, MPEG-1 audio and other voice coding applications included 
  4201.  
  4202. HardPak - CERAM Inc., ISA and EISA file compression board.  719-540-8500
  4203.     - 3.4 x 1.8 inch footprint (notebook, laptops)
  4204.     - 32KB on-board write-thru file compression cache
  4205.     - CERAM also has an SBus compressive swap-space accelerator for Suns
  4206.  
  4207. macDSP - Spectral Innovations, AT&T DSPC32-based accelerator.  408-727-1314
  4208.     - JPEG functions available
  4209.     - 30 MFLOPS on the NuBus
  4210.  
  4211.  
  4212. VCA-1  - Video compression accelerator for Sun workstations.
  4213.            Tel: (310)829-7733, FAX: (310)829-1694, Internet: spacecc@cerf.net
  4214.          Special-Purpose Hardware for Motion Estimation and DCTs
  4215.      Performs 8x8 DCTs in 21 microsec after first DCT at 52 microsec.*
  4216.      Performs 32x32 cross search for 16x16 block in 239 microsec.*
  4217.          (*Stated times are for a 25-MHz SBus.)
  4218.      Mounts in a single SBus slot.
  4219.      Included software allows user-transparent access.
  4220.      Price: $2,900 (subject to change without notice).
  4221.  
  4222.  Integrated Digital Video Boards - Miscellaneous Multimedia, Video Conferencing
  4223.  ------------------------------------------------------------------------------
  4224.  
  4225. VCI/oem - Vista Communication Instruments, Inc. +358 0 460 099
  4226.     - two AT-board H.261 video codec, PAL or NTSC cameras and monitors
  4227.     -56 kbps (64 kbps) to 2 Mbps, 64 kbps increments
  4228.     - H.221 framing and synchronizing     - H.241 network signalling 
  4229.     - H.200/AV.254 forthcoming standard for compressed audio
  4230.     - network interface boards available
  4231.  
  4232. MediaStation- VideoLogic Inc., JPEG compression board for ISA bus. 617-494-0530
  4233.     - works with VideoLogic DVA-4000/ISA motion video board, custom bus
  4234.     - CL-550 plus ADPCM and PCM audio support
  4235.     - Inmos Transputer for I/O scheduling
  4236.     - Microsoft Windows Multimedia Extensions and proprietary interfaces
  4237.  
  4238. DECspin - Digital Equipment CorpSound/Picture Information Network 508-493-5111
  4239.     - full motion, true-color (24-bit) and greyscale (8-bit black & white)
  4240.     - variable frame size and rate up to 640 x480 x30 NTSC true-color 
  4241.     - Internet or DECnet transmission and disk I/O of live synchronized
  4242.           video/audio
  4243.     - video teleconferencing using standard network protocols 
  4244.     - create and edit of audio and video sequences
  4245.     - voice grade live audio sequences
  4246.     - DECmedia DECvideo and DECaudio hardware and software required
  4247.  
  4248. ActionMedia II - Intel/IBM DVI PS/2 and PC/AT boards.  914-642-5472
  4249.     - i750 processor boards for capture and delivery systems
  4250.     - Microsoft programming support libraries
  4251.     - proprietary RTV and PLV compression algorithms resident, time and
  4252.           time/space VQ
  4253.     - Real Time  Video (RTV) algorithm 1.5 , effective 128x120 pixel
  4254.           sequence at 30 f/s.
  4255.     - RTV 1.0 is 128x240 at 10 f/s. 
  4256.     - Presentation Level Video (PLV) - extensive off-line processing,
  4257.           exploits inter-frame coherence.  
  4258.     - i750 processor capable of playing-back PLV-compressed 256x240
  4259.           sequences at 30 f/s. 
  4260.  
  4261. DVI Board - Fast Electronic U.S. Inc. laptop board.  508-655-3278
  4262.     - uses Intel i750 chipset
  4263.     - compress or decompress video at up to 30 f/s
  4264.  
  4265. EyeQ - New Video Corp. DVI boards for the Macintosh.  213-396-0282
  4266.     - uses Intel i750 chipset
  4267.     - 150 KB/s full-motion compressed video
  4268.     - T1 and Winchester integration paths
  4269.  
  4270. Copernicus 1000 & 2000 - DesignTech, 408-453-9510
  4271.     - DVI-based presentation and authoring systems 
  4272.  
  4273. Spectrum Signal Processing - DSP96002-based PC-AT board
  4274.     - up to four boards in cascade
  4275.     - other TI, Analog Devices and AT&T-based DSP offerings
  4276.  
  4277. Ariel Corp. - Dual DSP96002 PC-AT board with compression support.  201-429-2900
  4278.  
  4279. Capture I - UVC Corp., 16-bit ISA bus board.  was 714-261-5336, out
  4280.           of business now.
  4281.     - 30 f/s of 640/480 interlace capture and record (uses UVC7710)
  4282.     - NTSC or PAL input
  4283.     - VPC200/201 development board set - proprietary NTSC video codec
  4284.          (audio card required).  
  4285.  
  4286. Leadview  - Lead Technologies, Inc. accelerates an enhanced JPEG algorithm
  4287.    on ISA
  4288.  
  4289. IBM - near-term availability:
  4290.     (1) IBM United Kingdom and British Telecommunications plc. 
  4291.     - PC or PS/2 add-on boards by end of 1993
  4292.     - interface to ISDN 2 service (one or two 64kb/s channels)
  4293.     - BT also planning residential videophone product with GEC Marconi Ltd.
  4294.  
  4295. (2) IBM Japan PS/2 board 
  4296.     - uses GCTX64000 for H.261 
  4297.     - ISDN (narrowband 64kb/s ) and IEEE 802.5 LAN interfaces
  4298.  
  4299.  
  4300. Optibase 100 - Optibase, Inc. DSP-based compression/expansion boards.
  4301.    818-719-6566
  4302.     - supports JPEG
  4303.     - supports CCITT G.721 and ANSI T1.301 & T1.303  drafts (voice and
  4304.           music) 
  4305.     - and proprietary compression (AADCT, lossless)
  4306.  
  4307. Motorola - DSP56002 (fixed-point 40MHz version of the 56001)
  4308.  
  4309. AT&T JPEG coder (George Warner <warnergt@aloft.att.com>)
  4310.         - runs on a DSP3210 under the VCOS operating system.
  4311.       The coder can be used to simultaneously compress/decompress
  4312.       multiple images and/or be used in conjunction with other DSP
  4313.       modules to preprocess or postprocess the image data.
  4314.  
  4315.       Other modules available for the DSP3210 include audio coders
  4316.       (such as MPEG, SBC, CDXA, and G.722), modem/fax data pumps
  4317.       (V.32bis, V.22bis, and V.29), DTMF, call progress detection,
  4318.       sample rate conversion, and more.
  4319.  
  4320.  
  4321. MWave - TI, IBM, Intermetrics multimedia system, due from IBM in 1993. 
  4322.  
  4323. Misc. NuBus boards - RasterOps , Radius, Mass Microsystems, Orange Micro,
  4324. IBM M - - Motion.
  4325.  
  4326. P.OEM - Interated Systems Inc. fractal compression boards for the PC.
  4327. 404-840-0310
  4328.  
  4329. two desktop video conferencing products for Sparc's
  4330. with the Parallax XVIDEO board:
  4331.  
  4332. Communique! - desktop video conferencing products for Sparcs with the Parallax
  4333.               XVIDEO board:
  4334.         InSoft, Inc., 4718 Old Gettsburg Road, Executive Park West I, Suite 307
  4335.         Mechanicsburg, PA 17055, USA. email: info@insoft.com
  4336.         phone: 717-730-9501, fax: 717-730-9504
  4337.  
  4338. PSVC - desktop video conferencing products for Sparcs with the Parallax
  4339.               XVIDEO board:
  4340.     Paradise Software, Inc., 55 Princeton Heightstown Rd, Suite 109
  4341.     Princeton, NJ 08550, USA. email: support@paradise.com
  4342.     phone: 609-275-4475, fax: 609-275-4702
  4343.  
  4344. North Valley Research - video and other time-based media in a UNIX environment
  4345.         North Valley Research; 15262 NW Greenbriar Pkwy; Beaverton, OR  97006
  4346.         Phone (503) 531-5707, Fax (503) 690-2320. Todd Brunhoff <toddb@nvr.com>
  4347.  
  4348.  Boards Under Development
  4349.  ------------------------
  4350.  
  4351. Matrox - Matrox Studio line of PC boards will include a 64-bit MOVIE bus and
  4352.          JPEG compression.
  4353.  
  4354.  
  4355. ------------------------------------------------------------------------------
  4356.  
  4357. Subject: [99] Acknowledgments
  4358.  
  4359.  
  4360. There are too many people to cite. Thanks to all people who directly
  4361. or indirectly contributed to this FAQ.
  4362.  
  4363.  
  4364.